• Advertisement
Star Crossing Influence Based Pathfinding Debug Output
    4. Star Crossing Influence Based Pathfinding Debug Output

Other images in Star Crossing

Star Crossing Influence Based Pathfinding Debug Output

Sign in to follow this  
One of the big ideas in [b]Star Crossing[/b] is that the maps are highly dynamic. Stuff is "flying" around everywhere and I needed a way to make the agents do something a little smarter than just take the hit or get out of the way. This map shows the onscreen markers for debugging the influence mapping and its impact on the pathfinding algorithms.

Leveraging the physics engine, I found a way to dynamically mark nodes as blocked/unblocked. When they change state, I also have an influence value calculated around the nodes that have changed state. So instead of trying to calculate the influence on the whole graph continuously, I only calculate it when something that affects the blocked nature of the nodes changes.

The pathfinding engine uses A* and "(1+alpha*influence)*distance" based calculation to calculate the path. The real goal was to get the pathfinding to also take into account the size of the object itself, but that is still an open area. For now, it just navigates "around" objects instead of finding paths right next to them.

This cured several problems I had with the pathfinding:
(1) Entities would get stuck going around the corners of objects. Even though I put a mod into the pathfinding to take diagonal nodes out of the mix in these types of situations (e.g. the corners of the mining station), it still never worked for dynamic entities as I had hoped. This cured it.
(2) I had a problem where the miners would path diagonally into adjacent squares (think two abreast going diagonal). They would then "fight" to get past each other, but would take a while to do it...which looked pretty stupid. Now they work to keep away from each other. Looks much better.

There are probably some inefficiencies because of the same node being hit in an update cycle (nearby), but overall, the performance is quite good. With the debugging off, I am seeing frame periods of 4 ms on the iPad 2 for the scenario pictured.


© 2014
Sign in to follow this  
From the album

Star Crossing

  • 1 image
  • 0 image comments


Recommended Comments

There are no comments to display.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement