More Natural A* Navigation

xRegnarokx

So, I am creating a locked perspective 3D rpg with a grid movement system. At the moment I am thinking if only cardinal direction. Currently I use an A* to generate path for my enemies to chase my player, however it uses Manhatten heuristic due to 4 directional movement.

My problem is I want enemies to have a more varied movement pattern, and am unsure of the best way to realize a varied movement.

Currently I calculate the path 2.5 times a frame. I only use the first new position in the path to move and ignore the rest. So, each movement recalculates the path to keep an updated path concurrent with players movement.

Is there a way to vary the enemies movement pattern while using cardinal direction movement, and not breaking the benefit of A*? It is okay if the path is slightly less ideal, I'd prefer that over computer moving all the way toward player on one axis before switching to moving the other way.

axolotl

Sure, you can change your A* to be more random.

Here is the heart of A*:

A* selects the path that minimizes

f(n)=g(n)+h(n)

where n is the next node on the path, g(n) is the cost of the path from the start node to n, and h(n) is a heuristic function that estimates the cost of the cheapest path from n to the goal.

What you have to do is:
Change it to pick between ties at random.

xRegnarokx

axolotl Where would you change that? Is there documentation somewhere talking about changing it? Is that set in _estimate_cost()?

Thank you for the response.

I don't want it completely random, but rather if going up, or straight are both towards the player I Want it to randomly choose between those two options.

Imagine if there were two paths one prioritizing x and one y, I would want it to randomly choose between x or y in any given situation where there are two similarly weighted paths using the different axis.

axolotl

xRegnarokx I don't want it completely random, but rather if going up, or straight are both towards the player I Want it to randomly choose between those two options.

That's what this will do. It picks at random between ties. So it will never choose a longer path if a shorter one is available.

axolotl

xRegnarokx Where would you change that? Is there documentation somewhere talking about changing it? Is that set in _estimate_cost()?

I am not familiar with Godot's implementation so you will have to figure this out yourself I'm afraid.

xyz

xRegnarokx An enemy doesn't need to follow the calculated path at all times. Let it stray in random directions for a several tiles now and then and then recalculate and continue. Strays can happen more frequently and last longer the farther away the enemy is from the player.