H for diagonals as 1 or 1.4?

Unity Courses Ask
,
#1

Apologies here if I’m asking a question someone else asked. I tried looking for dups and didn’t find it.

So…I’m confused why we’re using 1.4 for H for diagonals if the units spend the same cost to move diagonal as they do up/down/left/right? I keep thinking it should be “1” for our use case.

I’m trying to think through the consequences here but wouldn’t that have the effect of the algorithm having some tendency to avoid diagonal paths because it thinks they are more expensive than they actually are?

Or does this negative consequence get canceled because you’re doing the same cost calculation for H and G?

#2

There’s a lot of complicated things in the pathfinding that I don’t quite understand the deeper underlying math for (or bothered to understand, yet), but I do know that a diagonal is not more expensive because it’s 1.4, while getting to the same cell without a diagonal is 2 because it takes to cells to get there. I believe it will favour horizontal and vertical over diagonal, but it will always choose the shortest path including diagonals

#3

As I think through it more, I think I can predict the consequences. I think what will happen is that the path finding algorithm will expand more horizontal and vertical paths than necessary. It will still find the shortest path with the diagonals for the reasons you stated about 1.4 being less than 1+1. But I think it will be less efficient than it could be on a more complex map with lots of obstacles because it will spend time exploring more non-diagonal paths than it should.

The value of 1.4 I think makes sense if you have non-grid based movement such as exploring an open world and the character has some consistent “velocity” regardless of what direction they move in.

#4

The distance from the centers of a square and a diagonal square are approximately 1.4 units, as opposed to the cardinal directions which are easily calculated as a distance of 1 between units. You can test this with the Pythagorean theorum.

C^2 = A^2 + B^2 A and B are 1, so 
C^2 = 1^2 + 1^2 or 1+1 or 2
C = Square Root(2) = 1.41421356237

This means that the actual distance travelled to a diagonal is longer, and the character will take 40% longer to get to the center of the square.

If the diagonal move is actually closer to the end target than the cardinal move, then it’s GCost may be higher, but it’s HCost will be lower, and that will make the FCost potentially lower. Remember that it’s the FCost that determines the next direction we consider, and getting closer to the goal (HCost) is a significant factor in calculating the FCost as much as the distance travelled (GCost).

#5

Definitely familiar with this and how it would apply to a real world situation and also to an RTS. What I’m struggling with is two things. Admittedly these are more of “curiosities” than anything.

  1. In our game, the way MoveAction works is like a king in chess. Even though the diagonal 1.4 times farther away it still costs only 1 “move” . For example if it cost 1.4 to move a diagonal then with MoveAction.maxMoveDistance of 4 we shouldn’t be able to move 4 spaces in a diagonal. The shape of the debug visual for MoveAction would be kinda jagged. So I’m wondering why we didn’t align our A* costing approach with the way MoveAction works?

  2. I’m trying to figure out the consequence of the decision. I ran some profiling out of curiosity and it seems that with a diagonal cost of 10, it visits more nodes and has to do more steps than if it were 14. This makes sense. If the zig zags bear no cost to the actual movement in game, then the algorithm is forced to explore all the zigs and zags. So algorithm run time is more efficient with 14. But I’m wondering how this would change if we had a map with lots of obstacles. I bet 14 would still be more efficient in terms of algorithm run-time but potentially 10 might find more optimal routes that 14 doesn’t because it explores more options.

#6

This is exactly why I prefer to design grid based games in Hexagonal formats. Six directions instead of 8, and the distance to the tile in any direction is the same. In a Cardinal/Diagonal format, the GCost will represent the actual cost of the move from point a to point b (including the 40% tax for diagonals). You could add a function that gets the current GCost of a given location, and only display the locations with a GCost that is less than the Move points.

This implementation of A* is far from exhaustive or perfect, and it wasn’t intended to be so. There is a tradeoof between speed and accuracy in any navigation algorithm.
The first time I did my own pathfinding, I completely left out GCost/HCost/FCost. Neighbor nodes were simply added to a queue, and it wound up searching a LOT more nodes before arriving at a solution. Often, the results when combined with obstacles would involve paths with lots of backtracking. I wound up calling that my Keystone Cop algorithm.

When I did my version of this course during the development stage, I made the choice to go purely Cardinal (N/S/E/W). I intentionally left out diagonal moves. Adding in blocking (i.e. you can’t walk or shoot through a tile with other characters in it), and you get a completely different dynamic, requiring different strategies than if the Diagonal directions are added and you can pass through occupied tiles.

#7

Thanks Brian. When I saw “14”, I felt like I probably missed something about how A* works. It seems like this is just meant to be a rough introduction to A*. Maybe at some point later in the course I’ll run that test and see how it performs with a more complex “terrain.”

I agree with your point about grids and hex grid. One of the reasons I took this course is because I have an idea for a game and was trying to weigh the options between normal grid and hex grid. The hex grid adds some complexity so I was happy to see that hex grid is addressed in the bonus. My first game probably won’t be a strategy game though. I think I need to start with something simpler.

Great course again!

#8

Ha! I just finished the “Unit Move with Pathfinding” lesson.

OK now the use of 14 (or 1.4) makes sense because the MoveAction code is updated to use higher cost of moving a diagonal in a future lesson. And yeah the GridVisuals shape also get updated as expected with a 1.4 cost to move a diagonal.

#9

Yes, and Hugo even says as much in the lectures. A complete breakdown of A* could be a course all by itself. We haven’t even touched space cost (for example, it might cost more to move through a forest tile than a clear one. It might cost less to travel on a road tile).

1 Like
#10

Oh yeah. Definitely. My main surprise was seeing the discrepancy between MoveAction and the algorithm but I just saw Hugo addresses that a few lessons later.

What’s so cool about the code so far is that it’s quite extensible and easy to modify. (And that goes for the A* code and anything else). So unless I’m doing a very dynamic scene or some more complex environment, I think I might prefer to modify this A* algorithm than to integrate one from the asset store.

I’ve tried a few other tutorials and I think this one from GameDevTV is the simplest to extend and modify because of how it’s written and how well everything is explained as we go along.

#11

This topic was automatically closed 24 hours after the last reply. New replies are no longer allowed.

Privacy & Terms