Posted in Hidden Asset Programming

A* pathfinding with weighted tiles

June 30th, 2014 - 3:03 pm

Until now, NPCs in Hidden Asset didn’t care whether they walked on the road or sidewalk. When finding a path from one spot to another, they’d always choose the shortest path. But having NPCs walking in the middle of the road without a care in the world is pretty immersion-breaking. So I had to implement some kind of way of having NPCs prefer walking on the sidewalk. This turned out to be much simpler than I had anticipated.

A* pathfinding works by checking potential paths between nodes until the destination is reached. For each node, you store how far you’ve traveled to reach that node. When the destination is reached, you just backtrack through the nodes with the smallest ‘distance traveled’ value. This gives you the shortest path to the destination. For my purposes, each tile is a node.

The distance traveled can just be 1 for each tile. So if you move through 4 tiles to reach the destination, the distance traveled will of course be 4. But because the pathfinding will choose the shortest path, changing this 1 to some other value for specific tiles or situations can have huge effects on the final path found.

One example of this is that I don’t give the same value when moving diagonally as when moving straight. While moving straight results in the ‘distance traveled’ to be increased by 1, moving diagonally increases it by 1.4. This is quite simply because you’re moving further when moving diagonally across a tile that’s a rectangle than when you’re moving straight across it.

A Pascal code example:

IF MovingDirection IN Diagonal
THEN Tile[NextLayer, NextX, NextY].G := Tile[ThisLayer, ThisX, ThisY].G + 14
ELSE Tile[NextLayer, NextX, NextY].G := Tile[ThisLayer, ThisX, ThisY].G + 10;

This code snippet takes the ‘distance traveled’ value (G) of the current tile and applies it to the next tile while increasing it with either 14 or 10 depending on whether or not it’s a diagonal movement (I use 14 and 10 instead of 1.4 and 1 in order to stick to integers — the individual values don’t matter, they’re only important in relation to each other).

However, I can also say that moving across a road tile will increase the ‘distance traveled’ value by an additional 10. The result of this is that an NPC will only choose to move across a road tile if sticking to the sidewalk means that he’ll have to walk at least an extra 10 tiles. Furthermore, I can tell the pathfinding that if there’s a pedestrian crossing on the road tile, don’t add the road ‘penalty’ to the pathfinding.

So I add a function call to the above code. This function returns the ‘penalty value’ for a given tile.

IF MovingDirection IN Diagonal
THEN Tile[NextLayer, NextX, NextY].G := Tile[ThisLayer, ThisX, ThisY].G + 14
ELSE Tile[NextLayer, NextX, NextY].G := Tile[ThisLayer, ThisX, ThisY].G + 10;

IF WeightTiles THEN Tile[NextLayer, NextX, NextY].G := Tile[NextLayer, NextX, NextY].G + TilePathingWeight(NextLayer, NextX, NextY, MovingDirection IN Diagonal);

Note that I only add these tile ‘penalties’ if the pathfinding function was called with WeightTiles defined as TRUE. I don’t add this tile weighting when pathfinding for the player character, for example, as it should be up to the player to decide whether or not to use the sidewalk and pedestrian crossings.

The result of all this is that characters will stick to sidewalks and pedestrian crossings, but if they really need to cross the road and they’re far from a pedestrian crossing, they’ll still choose to cross the road instead of taking a long detour. Here’s my NPCs demonstrating safe traffic behavior (though they don’t care about red lights):

Click to enlarge

Another use for this would be to have characters walk around corpses instead of over them. If there’s a corpse on a tile, just add 100 (or some other large value) to that tile’s penalty.

Comments are closed at this time.