A* Pathfinding Project

Grid Penalty not working as expected


#1

I’m really struggling to get my actors to choose what I think is the lowest penalty path. If you look at the simple example below an actor is moving from A to B but instead of following the green path they travel the shortest, higher penalty route.

By my (probably wrong) calculations the green path route should have a total penalty of 2750 but the direct route is 5250. If I increase the red penalty value to 12500 it works as expected (chooses the green path) but that seems like an artificial way to make it work.

I’m using version 4.2.2

Any thoughts gratefully accepted


#2

Hi

In addition to the cost of moving on a node, there is also a cost for moving between nodes. In fact, when all penalties are zero, this is the only cost that matters.

This cost is 1000 (Int3.Precision) * the world space distance between the nodes.
So if you have a node size of 1 it would cost 1000 to move between two adjacent nodes, or 1414 to move along a diagonal.

I think this is the part of the cost you are missing in your calculations.


#3

Ah, I see. So you’re saying it’s something like FinalCost = Penalty + MovementCost? I would have thought it would be FinalCost = Penalty * MovementCost. I’ll try again.

Thanks


#4

I think I’m still not understanding how penalties work, or they don’t work the way I expected. I’ve scaled all my penalties x10 so the min penalty is 6250 and max is 12500. Keeping to the example I gave this should mean there’s a total penalty of 27500 for the fast path and 52500 for the direct path. My node size is 3 so the total movement cost you spoke about for the fast path should be 16242 and the direct path should be 12726. Adding movement cost with penalty would mean the fast path is 43742 and the direct path is 65226. So I would think it would prefer the fast path, but it still doesn’t. Of course this is only how I imagine you’re calculating the costs so I could be way out.

Like I say, I can make it work with this example if I use ‘fake’ values, rather than being proportional to my own game’s penalties (0.5 - 2.0). It may be better if you could suggest a range of values I should use? I have about 6 different surface types I want to simulate.


#5

If I have done the calculations correctly, I still find the direct path to have a lower total cost than the “fast” path.

# Assuming penalty for red tiles is 12500
# Penalty for green tiles is 6250
# Node size is 3

# Direct path
redTiles = 4
greenTiles = 0
diagonals = 3
straight = 0
cost = redTiles * 12500 + greenTiles * 6250 + diagonals * 3000 * math.sqrt(2) + straight * 3000
# cost = 62728

# Fast path
redTiles = 2
greenTiles = 5
diagonals = 0
straight = 6
cost = redTiles * 12500 + greenTiles * 6250 + diagonals * 3000 * math.sqrt(2) + straight * 3000
# cost = 74250

May I suggest reducing the green node penalty?


#6

That’s a nice “code” explanation, thanks so much for that.

The way you work out the cost is surprising but that’s probably because I don’t understand what’s going on so a couple of questions if that’s OK.

  • Why don’t you account for diagonal penalties?
  • What is “movement” cost and why is it not proportional to the penalty?

You’ve suggested I reduce the green node penalty and yes, that will work in this instance, but only because I have 2 penalty types in the example. Like I say I have about 6 different tile types so how will I work out what penalty values to use? In my game I have preset delays that tell how long it takes to move from one tile to the next so just making the Penalty proportional to these delays doesn’t work.

Thanks


#7

Hi

Yeah. So that the penalty is just a pure additive value is just due to that it has been that way historically. Breaking backwards compatibility is not something I want to do. Ideally I would want to use penalties that are proportional to the movement costs though. I’m thinking of adding it using compiler directives together with some automated code that reverts back to the old behavior if it detects one has upgraded from an older version.

Essentially the cost of a path is

cost = cost of each connection along the path + the penalty for every node on the path

#8

That would be a most awesome thing if you could because right now my actors look drunk :slight_smile:

I’m sure you have other better things to do and you probably find it hard to get time to work on this, but if you were to go ahead with this change, any thoughts about when you might be able to do that?