Ask for 2D pathfinding example/code

Unity Engine
1

Hi! I’m looking for a working code of 2D pathfinding! I already checked a many type of code/downloadable content, but I didn’t find a proper one… very stressful!

I have a few conditions:

  • Fit for 2D top-down game
  • Grid-based A* (best), or non-grid based
  • Contain collision-avoidance (enemies/characters must avoid each other)
  • Agents don’t “merge together” at the end of the path (stop past to each other)
  • Can adapt to dynamic obstacles (moving stuffs, just built building)
  • The usage of the code should be easy to understand/apply
  • FREE to use if downloadable

I downloaded a many code but most of them didn’t contain the collision avoidance future or very complex and I can’t figure out how to use…

Would be awesome if someone can send me a link or provide code (and instruction), I would appreciate as I looking for long time ago! Please help me, thanks in advance!

2

I would suggest learn to code it yourself as you would understand better and can do it the way you want plus is not that hard if you really wanna learn

3

Yes, it’s obvious! This would be the best way, and I already tried to do it (know the logic behind A*) by myself but I can’t get a proper one… I checked tutorials but they became too complex even they started very simple.

If you can suggest me a tutorial which cover all of the points I defined and don’t became too complex (by lot of extra function, unlogical/chaos code etc…) then I will give it one more chance! Thanks!

4

if it get too complex you can always ask somewhere to try to understand if some of the tutorials don’t cover everything you could learn from different places and put it together if you stuck somehow post it up sure someone will be able to help .
if you feel lost you could always break it to small part and try to understand …as for tutorial i don’t really know much where is the good ones …when i learn to try my own one i just google here google there and learn as much as i could and then put it together to do the way i want …
i start of from here A* search algorithm - Wikipedia

5

I cannot, but I can suggest an extra way to break the problem into smaller pieces to increase your understanding of the next tutorial you tackle.

When you implement A*Star in a game engine you’re actually doing TWO things, and I think this is where a lot of people get tangled up.

Part 1:

The actual AStar algorithm is just a graph traversal searcher with heuristic. It’s super-dry super-abstract, almost impossible to really do anything useful with in its own regard. This is the part that is largely described in the Wiki page and other tutorial pages about AStar. It is literally “how do I get from this data structure to that data structure.”

Part 2:

This is how your game, basically all the GameObjects, components, linkages to get from one place to another, area connections, etc., how that maps to the graph. Remember, A*Star only operates on a graph, and a graph is just a collection of nodes and some lines linking them together.

Obviously it’s not practical to link every millimeter of your game world together because the graph would be massive, so there is a mandatory simplification of the game world that must happen.

With a grid it is slightly more straightforward, but then you also must map how to incur costs such as “infinitely high cost” (a wall you cannot walk through) or “kinda high cost” such as mud or mountain or sticky ground. These types of world nuances must be encoded into the graph as the costs for each part of it.

So keep these two things in mind on your next tutorial. The first AStar routine really can just be done once. It’s just super-dry math. The second part is the hard part, the part that you must make decisions about as a game engineer. That’s basically why you can’t just “drop in” an AStar package because all it would get you is Part 1 above.

1 Like
6

Thank you guys! I will try to do it on my own as I didn’t get any example script. Would be the best if I code the whole algorithm, but an example to the collision avoidance part would help. This is my biggest problem and the most wished function too. I already found a quite simple A* but the collision avoidance missing from it (of course…).

7

Astar does not handle collision avoidance. It’s up to you to design a graph so that a valid path through the graph actually avoids collisions with your game world.

If something walks into the graph pathway, it’s up to your code to recognize that and appropriately either disconnect that node of the graph, or else increase its cost of traversal, to cause agents to tend to avoid it.

This function is provided in the Unity NavMesh by placing a NavMeshObstacle. At the corners of buildings and whatnot, the avoidance is handled by the “AgentRadius” setting on the bake window. So when you’re implementing your own AStar (in lieu of just using Unity’s NavMesh), it’s up to you to implement those functions however you see fit.

In fact, if you feel brave, you can actually leverage Unity’s navigation yourself in a dynamic context, at least according to this tutorial:

Caveat: I have not used this myself. Go try it out, it’ll save you hassling with graph traversal, but instead you’ll need to learn the NavMesh system pretty thoroughly I imagine.

And when you get it working, report back to us here so we know it works!

1 Like
8

Oh thank you :wink: You gave me a good tip how a collision avoidance working. Very obvious what you wrote me (If something walks into the graph pathway…), but I thought it a different -more complex- way unnecessarily. Now this whole collision avoidance looks easier, but I’m pretty sure it will be more difficult when I try coding.

The steps (after the A* pathfinding part ready and working):

  • Check through the path for collisions (to see if an other agent move in or block the way something)
  • Recalculate path from the player actual position to the target

But if I imagine this method a bit further I notice a few issue:
1 - This can be a costly solution! Imagine if I have many agents and all of them have the same target (ex: 500 soldiers move to the same position). Even if I use heap-optimisation and coorutine, they will recalculate their path every x times (let’s say twice a second) because the agent’s will get the very similar path and they will block each others path constantly.

2 - Or what if I have only two agents and the target located in a narrow dead end corridor? So they move along their path and they reach the enter of the corridor at the same time. Then they move to the corridor at the same time, overlap each other… (not realistic) .
3 - Or if one agent step in the corridor before the other, the last one stop moving as the first block the only way and it can’t recalculate (can’t reach target). Of course the last one should follow the first agent and stop behind it when the first reach the target.

4 - Or if 8 agent block the target square (finish their path around the target), the remaining ones can’t finish their path as the way fully blocked.

Now it’s looks very complex, and who know how many more problems occur during testing…

I know about the unity’s navmesh, and I already tried it. Works really well but it’s not for 2D and use mesh nav instead of grid-based. My spare solution would be this… use 3D world with top-down camera and render primitive objects with sprites. So everything would look like a 2D top-down game, but I can use the NavMesh as a perfect pathfinding solution with its built-in collision avoidance. Unfortunately I can’t use grid-based style movement here, but better than nothing!

9

You could probably do this by having the navmesh exist flat the way it is intended, and have an invisible pathing agent following that navmesh, then over in 2D land (which exists “on the wall”) have your agents basically follow a transformed position of the navmesh.

It would be some variation of:

Vector3 NavMeshAgentPosition =  ... whatever

Vector3 TwoDimensionalPosition = new Vector3( NavMeshAgentPosition.x, NavMeshAgentPosition.z, 0);

That way you could play in your preferred 2D land while getting all the NavMesh benefits.

10

Thanks again! I will try this as I’m curious how the “simulate 2D behind a 3D world” things works in action!

11

This mechanism can be very powerful in games, such as for moving cameras or other things via a “proxy” object that actually has all the move logic on it, and instead of placing the visual on that object, you can get certain functionalities by simply “following” it with another object.

12

Can you explain me how do you mean this proxy object thing? Basically, if I create an “invisible” 3D object -like a cylinder- and create a visual (sprite on a plain?) then set the visual as a child of the cylinder? In this case I can use all of the functionality of the NavMesh pathfinding meanwhile it will looks like a simple 2D sprite… but I’m not sure is it what you think under the “proxy object”.

13

Generally anytime you have one thing chase another is what I mean by proxy object.

This may be more than you need, but purely based on your first post, wanting a navigable 2D grid:

  • make the 2D navmesh dynamically using the UnityEngine.AI dynamic navmesh API (this of course has to be flat, “on the ground”)

  • put an invisible agent on that mesh to make it go to specific places under the control of Unity pathing

  • meanwhile have another sprite in 2D (vertical plane) that uses the coordinates of this invisible agent to set its position

It might not apply, depending on how you are choosing to proceed.