W.U. 23: Pathfinding Test

With the outdoor map I made it was clear that I needed some pathfinding for the characters.

Typically this is achieved with overlaying a cell grid on your map, or perhaps manually placing markers/nodes on your map indicating possible pathways.

Then an A-star pathfinding algorithm is let loose, finding the optimal path from one spot to another with the help of the aforementioned cell grid, or node map, or what-have-you.

(Unity Pro has a really nice Navigation Mesh feature but since I don’t have Pro, I can’t use that.

There’s this: Certain Logic’s Navigation Opensource Framework, and I’ll probably take a look at it some time.)

My problems were:

  1. This is a strategy game that features a gridless map (like Skulls of the Shogun or Phantom Brave), so adding a grid wasn’t very appealing to me at first.
  2. The characters consume resources to move (i.e. action points like in the old XCOM: UFO Defense). Among the costs for movement, the slope or angle of the terrain influences this very much. Steeper terrain costs more to travel to. Coupled with a gridless map, this means the exact slope of the terrain has to be used. A cell grid would be a coarse sampling of the terrain, and the resulting calculations of angles from that would be inaccurate, leading to discrepancies in cost to a unit’s action points.

To get accurate measurements, I’ve had no choice but to make hundreds of raycasts on-the-fly.

Off in the night, while you live it up, I'm off to sleep.

This unit can’t move very far up, as that consumes more stamina points.

But this was clearly taxing on computer resources, so I had to do something about it.

My first attempt was to make the cell grid very tiny, about 0.1 meters per cell! This turned out to be even slower than without pathfinding because of the amount of cells to consider.

Waging wars to shake the poet and the beat

The path up the mountain should be included in the movement range, but how would that be calculated?

I tried ditching the pathfinding and used a brute force approach, but it was clearly very slow and unwieldy.

I hope it's gonna make you notice someone like me

The brute force approach to include detours in the movement range was inefficient.

I had to make concessions. I focused on giving pathfinding to the enemy AI movement only instead. Movement range calculation wasn’t something I can solve anytime soon.

I tried a pathfiding solution again, but this time, the resulting path would only serve as a guide to detour around obstacles, not as the actual path to be used (to keep movement costs accurate).

I can get away with making the cell size coarse this time, 1 meter in size. While this means a really optimal path won’t be taken, at least the enemies won’t mindlessly keep running toward walls.

It worked nicely, but my characters still end up moving through impassable terrain, and even other units, bumping them off-course.

Valve’s presentation slides on The AI Systems of Left 4 Dead shared a nice simple solution: a simple steering behaviour on top of the pathfinding. I realize, despite my ignorance, that steering is probably a common method anyway.

While it still manages to bump other units slightly, at least the enemies now have some semblance of intelligent movement. A more sophisticated approach would be squad formations.

Furthermore my little Influence Map project may come in handy later on, to give a more tactical decision-making process to the AI.

Amidst all the experimentations, Git handles all the code changes gracefully.

Amidst all the experimentations, Git handles all the code changes gracefully.