Next: The Floodfill Algorithm
Up: High Level "AI" Algorithm
Previous: What is it?
Contents
The ideal algorithm should take into account the time used for acceleration,
deceleration, turning and probability of running into a wall (due to
accumulation of errors). Such algorithms do exist. Indeed, to solve a
maze given a set of known walls, we simply have to study solutions to
solve a state-space search problem. Dijktra's algorithm, A* (pronounced
A-star), C* all try to solve general state space search problems and find
the optimal solution.
Unfortunately, all of the previous mentioned algorithms require quite a
bit of memory and processor resources. By giving up a little bit of
optimality, we can restrict the problem enough to use a much more
efficient algorithm called ``floodfill''.
Tak Auyeung
2003-09-29