December 26, 2007 § Leave a comment
Have just spent all day reading, coding, pulling hair out, deleting code, and starting again… but I can finally say that I’m getting somewhere! I decided that we’re going to need some path-finding in the engine to perform user interaction intuitivly, and sat down to implement the A* algorithm. One thing I don’t understand is why there seem to be about 5 different descriptions of the algorithm… Either way, I worked through it, and now thoroughly understand the algorithm’s basics, and have a worked system. My algorithm has turned out this way:
- Create some holder lists. I have a list for all nodes, a priority queue for the open list, and a simple list for the closed list.
- Add the start to the open list. Standard step, push the start node onto the open list, with a priority of 0.
- Begin looping. Until the open list is empty
- Get the current node. Dequeue from the open list, which uses a min-heap to give the node with the lowest cost.
- Fetch all sucessors. Query the world with for all sucessor tiles (neighbours) around a point.
- For-each sucessor:
- Find a node. I find a node from my “all nodes” list that has this tile attached to it. Nodes are an adapter for tiles, and allow parenting. If it’s not in the “all nodes” list, I create it and append it.
- Update the node. If this node is not on the open or closed list, and the cost of moving from the current node to this sucessor node is less than the original cost of this sucessor node, update the G & H values for the node, and change it’s parent to the current node.
Seems to work a treat! I haven’t done any profiling yet, currently I’m trying to reduce the current coupling between the world and tiles with generics to make this even more reusable (everyone hates class coupling!), but to be honest, this is not a realtime game, so I’m not sure it’s essentially that this path finding is blazingly fast so I will leave optomization for now.
Here’s a shot of the results of path finding, the orange path is the result of path finding, to the tile near the water. I updated the tileset slightly as well, and improved the alignment between tiles slightly – so hopefully it looks a bit more sechsey 🙂