all #1 #2 #3 #4 #5 #6 #7 #8 #9 #10 #11 #12 #13 #14 #15 #16 #17 #18


+ +

+ +

The Maze Solving Problem
Michael Chernobrod
John Bruneau on Mar 27 2003 Digital Insights

A project by John Bruneau and Michael Chernobrod

This is a simple example of AI:artifical intelligence. In this particular case, we present a simple AI based on Valve's Half-Life engine. This is actually a MOD:modification for a game, that uses another utility called HLB_bot, which is an AI of a character in the game.

We use the chatacter to demonstrate the model of finding the way through a maze. It coordinates itself placing waypoint marks on the way, every 200 steps, which is specific parameter measure of the engine. In addition bot is able to perform random rotational moves, so the change of traectory could be possible.

Algorithm behind bot's logic is extremely simple and limiting the bot to make rather stupid moves sometimes. When running the simulation for quite a while you can see the progression of the bot, enabling it to build up a network of connected in between nodes, or waypoints.

Using these waypoint the bot can navigate through out the space. After a big amount of time we can assume that bot while be able to cover the whole map, without getting stuck at any of dead ends.

We can see the storing mechanism in real time-these are the waypoints that are being placed (look for blue rods). Self-learning mechanism being created with ability of the bot to store environmental data and use it later for navigation. All the process are happening in real time in OpenGL grpahics environment.

Download movie for the project 8,406Kb

edit post | sent this page to a friend | printer friendly


last 5 articles posted by Bruneau

:: The Maze Solving Problem - Mar 27 2003


about | contact | credits | subscribe