All entries for Thursday 04 May 2006

Road Pathfinding Complete

Managed to finish the javacc a little quicker than I had expected, so spent the evening doing some more work on the road networks. While the actual method of placing roads is still a little shakey (half squares at a time, no dragging) it builds up a graph data structure to store the network. Currently every square is a node in the graph, but I've already implemented the concept of a "path" from point A to B, so just need to add a little extra functionality to remove straight lines as nodes.

On the pathfinding front, I think I am probably done. I did hope (before I started coding) that I'd be able to abstract rail/road networks into a single "network", but have opted not to, at least for now. Although they share many characteristics, signalling on rail networks is going to be a big enough pain that having the road network separate will make my life easier.

I chose A* pathfinding for a few reasons really, a) it seems generally to be the "fastest" of all the graph searching algorithms, b) OpenTTD uses it, so it must be good, and c) It's not as hard to implement as it might first seem. For a bit of extra reading, Wikipedia is a good place to start, while A* For Beginners does a fairly good job of explaining it.

No screenshot this time, just a video of the pathfinding doing it's stuff. A snip at 546K (xvid) it just illustrates a vehicle knows where it's going. Animation around corners and non–tiling road textures are the least of my worries at the moment :).

: 04 May 2006 08:18 |  Tags: Network Pathfinding Road |  Comments (0) |  Close comments |  Report a problem