Lost again…

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:

  1. 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.
  2. Add the start to the open list. Standard step, push the start node onto the open list, with a priority of 0.
  3. Begin looping. Until the open list is empty
    1. Get the current node. Dequeue from the open list, which uses a min-heap to give the node with the lowest cost.
    2. Fetch all sucessors. Query the world with for all sucessor tiles (neighbours) around a point.
    3. For-each sucessor:
      1. 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.
      2. 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 🙂

 Overload Path Finding in Action

Advertisements

Tagged: , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

What’s this?

You are currently reading Lost again… at Cycles.

meta

%d bloggers like this: