Thursday, December 30, 2010

Path finding

Path finding is a very important part of any rts, so I wanted to get that done early.


Been working on path finding yesterday and today, and have got it working. Units in the game now go around water, cliffs, and buildings. and try to avoid other stationary units.

First I went with a classic grid based A-Star path finding system. I then setup 3 layers of costs so they could be updated independently: Map, buildings, and units. with a value of -1 meaning it's uncrossable.

My first implementation run in 21 secs, but with a bit of work and a lot optimisations I got it down to 38 ms for a big map, and long distance path. Would still like to get it faster but.

Grid based path:




I worked out a nice way to make the grid based path better is to running it though an A-star again but this time treating each point as a node, and letting the connections be made as lines. Not sure if this is the best way or if any one else has though of it before.

Doing that I get:



Which is a lot nicer. It is still a bit slow doing long distances, as it has do lots of line to square collision checks, but I think I can fix that.

No comments: