Colliders and A* Pathfinding

[brigas]

I have been looking into A* pathfinding theory and I understand it essentially is inputing a grid of walkable nodes into a function that assigns scores to neighbouring nodes until it finds the most optimal path from point A to point B.

However how does this work in a case where a given character needs more than 1 cell of space to move?

For example if a character was 1.5x1.5 cells wide, how would the algorithm need to be changed to account for this extra needed space to move? Since I have characters that can be as large as 5 cells wide, I was wondering if anyone could point me to the solution.

Thanks!

[matkoniecz]

A* is working on a graph - https://en.wikipedia.org/wiki/Graph_(discrete_mathematics) https://en.wikipedia.org/wiki/A*_search_algorithm#Example

Generating one from 1 tile grid is easy one, but you may generate also more complex ones.

@brigas

For example if a character was 1.5x1.5 cells wide, how would the algorithm need to be changed to account for this extra needed space to move?

Graph generation used by A* will be different, depending on specific goals. A* will work in the exactly same way.

Is character moving from the tile center to tile center? On any location, not only in the center (significantly harder)?

@brigas

Since I have characters that can be as large as 5 cells wide

You will have multiple graphs for different sizes.

BTW, NavMesh may (or may not) fit you needs. See https://docs.unity3d.com/Manual/Navigation.html

[brigas]

@matkoniecz

A* is working on a graph - https://en.wikipedia.org/wiki/Graph_(discrete_mathematics) https://en.wikipedia.org/wiki/A*_search_algorithm#Example

Generating one from 1 tile grid is easy one, but you may generate also more complex ones.

Graph generation used by A* will be different, depending on specific goals. A* will work in the exactly same way.

Is character moving from the tile center to tile center? On any location, not only in the center (significantly harder)?

You will have multiple graphs for different sizes.

BTW, NavMesh may (or may not) fit you needs. See https://docs.unity3d.com/Manual/Navigation.html

moving from center of tile to center of tile is totally ok, what would the graph generation look like to accommodate for different character sizes?

My terrain is described by a 2d(x,y) byte array so conveniently open cells could be used as nodes.

But some characters take more space than 1 unit of the grid, many times by uneven amounts (1.5, 2.3, etc)

[matkoniecz]

@brigas

moving from center of tile to center of tile is totally ok, what would the graph generation look like to accommodate for different character sizes?

Generating new grid for pathfinding from grid of obstacles at a given size would be easy.

now: tile [x, y] is accessible if [x, y] is not blocked

for colliders >1 and <=2: tile [x, y] is accessible if following are not blocked: [x, y] and all its neighbors

for colliders >n and <=n+1: tile [x, y] is accessible if following are not blocked: [x, y] and all tiles in range (how range is defined depends on how exactly unit moves)

(untested, but basic idea “generate new graph” is certainly correct)

@brigas

But some characters take more space than 1 unit of the grid, many times by uneven amounts (1.5, 2.3, etc)

But obstacles take full tiles, right? Is there any case where 1.1 would fit and 1.9 would not?

[brigas]

@matkoniecz

Generating new grid for pathfinding from grid of obstacles at a given size would be easy.

now: tile [x, y] is accessible if [x, y] is not blocked

for colliders >1 and <=2: tile [x, y] is accessible if following are not blocked: [x, y] and all its neighbors

for colliders >n and <=n+1: tile [x, y] is accessible if following are not blocked: [x, y] and all tiles in range (how range is defined depends on how exactly unit moves)

(untested, but basic idea “generate new graph” is certainly correct)

But obstacles take full tiles, right? Is there any case where 1.1 would fit and 1.9 would not?

Yes all obstacles are 1x1 centered on the grid.

I see, so I just mark nodes that would normally be open for a 1x1 character as unwalkable if they don’t create at least a 2x2 area with the other open nodes adjancent to them?

And for each different character size I would feed a different array of nodes based on their size.

Thanks!

[matkoniecz]

Yes, that is one solution.

You can also check access dynamically during pathfinding (for example for a massive map or if you have many, many different sizes).

Good luck!