# A* Pathfinding Demo - Free project

Hi

In the past few weeks I have developed a A* pathfinding system.
The focus is to provide an out-of-the-box pathfinding system.
The script can adjust itself after the terrain height so it can take angles into account (currently max angle and angle cost), that can be useful if the unit need to walk over a mountain, then it is good to look for a place where the mountain isn’t so high, this is illustrated in image 1.
Take a look at my demo here: A* Pathfinding Project and tell me what you think.

Make the player move by clicking on the terrain, the player will then calculate the path and move towards that point.

Looks and sounds awesome.

I wanted the player to walk through the maze, but he cheated and found a shortcut.

This does indeed look and sound awesome!!

And, releasing the project from free (i can’t wait)… I am currently toying with Pathfinding myself, so I may be forever in your debt.

Brilliant stuff.

Matt.

Hi

Now the demo is updated with a very tricky maze and a better camera controlling system, (wasd, Numpad:4,6,2,8, + and -).

And here’s a screenshot of the GUI.

How many agents do you think might do pathfinding at the same time? Btw great work.

Oh, nice!

It’s about time Unity got one of these!

IIRC, A* is decently fast, and depending on the implementation details there are certian optimizations you can build into it.

It looks like calculating one unit causes no noticeable slowdown. I’m guessing any lag would occur when the path is first calculated, and not every frame.

If so, a yield statement should do the trick. If I select 200 units, and it takes the game 3 seconds to calculate their path, I have no problem with that as long as the game doesn’t freeze for those three seconds.

The trickier issue would be how A* responds to obstacles being added to the path, and units avoiding other units.

I’ve heard there are some implementations of A* which are recursive, so that within each cell there’s a grid of smaller cells which are used for for the dynamic stuff, and only a small group of these smaller cells are called at once, to get the unit from one cell to the next on the larger grid.

More details on A* in general here:

Hi

I’m actually using the yield statement in the script.
And, since all units are using the same grid to operate on only 1 unit can calculate the path at one time, I found it VERY time consuming to copy the grid every time I needed to use it. Of course you can have several copies of the grid the units can operate on but I think it is faster to only calculate one path at a time (taking lag into account).

WarpZone: When you mentioned the 200 units thing, I tested it, and it actually worked with a decent amount of lag and it took about 3 seconds.
For the coming versions I also plan to fix some functions which can recalculate the grid in only a small area, for example when you have placed a building there in runtime.

That sounds good, do you have any link?

SREENSHOT
50 units has calculated the path. Game froze and it took ≈ 0.1-0.2 seconds.

http://www.policyalmanac.org/games/aStarTutorial.htm

I’m sorry I can’t find the specific article I read which referenced the recursive A* technique, but it’s pretty straightforward. Imagine a grid-based maze. This Macro-level A* grid only needs to know how to get from one point in the maze to any other point in the maze. Next, imagine that each cell in the big A* maze has its own micro-grid within it, perhaps 16 cells by 16 cells, which is recalculated every time a unit enters that Macro-cell.

The Macro-grid never needs to be recalculated, and the micro-grids are only 16x16, so recalculating one of them doesn’t take too long.

If you drop one new feature into every cell on the grid, this would slow down just as much as subdividing the macro grid 16x. Probably even slower, because of the extra overhead. But for a maze-based game this would be a nice optimization.

Then again… Unity is more of a sandbox game engine anyway, isn’t it? Perhaps the article I read is no longer applicable.

Also it sounds like your methods for recalculating small sections of the grid is pretty much the same net effect. Another possibility might be for each unit to constantly update their own micro-grids around them. The point was for units to get from point A to point B using the Macro-grid, and only solve the micro-grids when there are unexpected surprises that need to be navigated around.

It amuses me that it was actually 3 seconds! I was just guessing a number. XD

It’s a shame about the game freeze in the 50 units scenario though.

Is it possible to yield more often? Lag is better than a game freeze. But longer calculation times are better than lag, as long as it’s within reason…

(Maybe even give the user an option tucked away in a pause menu, since the actual delay will depend on the user’s system. And of course, definitely scale the max # of units, for the same reason. But, of course, these are implementation details for individual games and beyond the scope of your work here.)

When I ran the 50 units test I had the settings on 0.003 seconds/frame the script can use as maximum, usually I have it on 0.001 seconds so that can explain the freeze, also I can chose to yield one frame between each new path, that was turned of so it would also contribute to the lag.

You can see the full list of options here: A* Pathfinding Project All pages are not finished yet, and the linked page does only show the interface for the main script, not individual unit options (like max angle).

PS: Those two articles were exactly the ones I read when I started with this

The speed is more than fast enough

In a realistic environment there are never 50 distinct entities / group requiring to search a path at the same time, especially not such long distance paths …

Looks very interesting and powerfull

cool,any solution for avoiding obstacles(other units) when running on path??

No, not in the current version, I hope I can find a solution for it in coming updates.

Somebody’s never played Total Annihilation…

Hi

Now the project is released!