So, I’m pretty new to AI in general, and am trying to implement a tree-based search from a textfile input (a maze). An example would be:
||||||||||||||||||||||
| || | | |
| |||||| | |||||| |
|||||| | P |
| .| |||||| || ||||| P = Start
| |||| | | | / . = Goal
| ||| ||| | | /
|||||||||| |||||| | /
| || | /
||||||||||||||||||||||
I understand the basic algorithms in general (BFS, DFS, A*, etc.), but I want to make sure I’m implementing them correctly, and not somehow cutting corners because “I know where the best path is”. My basic idea is:
- Parse the file into a 2D array
- While parsing, if I encounter
P, note the Start index - While parsing, if I encounter
., note the Goal index - Begin at
Index(Start), and evaluate surrounding [blank] spaces - Create
Nodes for these, and add the appropriate actions to the current Node’s available actions — Add theseNodes to myfrontierque - [continue whichever algorithm from here]
So I guess my main question is, am I generating my “world” correctly? Is it right to not really create Nodes until I encounter them during the search? It seems wasteful to get to a [blank] space, scan the surrounding 4 directions for other [blank] spaces, and if they exist add them to the available actions and create Nodes for all possible actions.
Another alternative would be to generate Nodes as I encounter the [blank] spaces, but this would be hard (since I wouldn’t be aware of the upcoming blanks) … should I parse the file completely, and the traverse the stored array to create all possible Nodes/Links/Actions? Or is that considered cheating somehow…
An object-oriented programmer’s instinct on this sort of problem is that at some point they’ll have to instantiate some sort of Node object, but you really don’t. You don’t even need to create a 2D array.
The path-finding algorithms are described largely in terms of sets. You can write very clear implementations by parsing your maze into sets of (row, col) tuples. This lets you write operations like the following:
(row, col) = starts.pop()
neighbors = {(row+1,col), (row-1,col), (row,col+1), (row,col-1)}
neighborSpaces = neighbors & spaces
unvisitedNeighborSpaces = neighborSpaces - visited
neighborGoals = neighbors & goals
Here starts, spaces, and goals are sets you created from parsing the file, and visited is updated over the course of your algorithm. Note that set operations are generally O(n), where n is the smallest operand. That means neighbors & spaces will only do 4 comparisons, no matter how many spaces in your maze. It’s not the most efficient implementation possible, but it’s efficient enough, and the clarity it buys you is well worth it.