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.


  1. Packers And Movers Hyderabad
    In loading and unloading is done carefully by experienced workers. In addition, hyderabad packers and movers unpacks the delivery at the target, very efficiently & with maximum care.

    Packers And Movers Hitech City
    Packers And Movers Lingampally

  2. Packers Movers Kolkata are please to help people in the most meaningful manner we did whatever
    makes us feel comfortable. We love to help people in the best manner as we can do. By giving you our
    services we feel like we are on the top of this world. You just have to keep faith in us and we will be
    their anytime you wanted. Join hands with us and forget all your worries regarding shifting and packing
    and moving from one place to another.
    Packers and Movers Kolkata