Multiple graph types


I’m building a defense rts style game and have a few questions about A* in relation to it.

In the game the player places circular walls to keep mobs form attacking the base. All of this works fine using a grid graph and updating it when the walls are placed. However I want the user controlled units to walk on the walls and this makes for a bit of a mess on the grid graph. The scale of the wall mesh in relation to the ground is pretty small as I want the feel of the world to be massive (I E the walls feel like they are several football fields away form the base). I can make the graph ridiculously dense and get the pathing on the wall to work, but that seems a bit excessive. I was wondering if I can do both a grid graph and a point graph in one scene? The point path would be setup along the wall and the grid along the ground.

I had already started working on my own point path code to manage the wall pathing when I saw that A* has one already.


Can a point grid be dynamiclly updated?
Can the seeker be told which graph to use if there are multiple graphs in the scene?

If this is possible it would save me some time and I would probably start giggling like a schoolgirl!

Thanks for any help!

Are you using the Free A* pathfinding?? This would be perfect for a Recast graph, seeing as you would only need one :slight_smile:

Other wise you should just use a 2nd grid graph, and set the masks on the new one only for the Walls

You don’t need to specify what graph to use, A* will figure that out for you, just make sure that you make the edges of the wall unwalkable (Or set max clime to an unwalkable value) so your units cant move from one graph to the next~

Hope that helps!


Hey Burdock,

Thanks for the quick response. I’m currently on free but would have no problem getting pro if the raycast graph would solve the issue. Form what I have read though the the raycat graph update is pretty slow. Since the mobs break the walls it might effect the user experence to update during gamepaly. The user builds the walls dynamically as well. That seems like to much for the raycast graph to be practical. As for using grid graphs In order for them to map the top of the walls with enough grids to be walkable I have to set the graph in the 600x600 range witch also seems a little high.

What is an acceptable graph size in general? Based on the tutorials it seems that more then 400x400 is pretty high.

Update Looking thought the the DoorController code I found that indeed the tags can be updated using bounds. I’ll play around with that some and see if I can get it to work as intended. I’m still a bit weary about the size of the graph I will need to use for the wall pathing to work as intended.

Also can the tags be dynamically set? Can I say make all the grids on the top of the wall set to a different tag when I update the grid graph? Or can I have all the grids on my second grid grap set to a tag?

I could do one 100x100 graph for the ground and one 600x600 graph for the top of the walls if I could set the tags on the fly.

Well… graph size does not directly effect performance:

If you set the Graph Update scene size too only be as large as the built or destroyed wall it will only scan that number of nodes… Having a larger grid does not effect the performance of this much at all:

If you run this on a separate core (Up to 8 available in A* pro XD) the performance impact should be pretty small:

I can run a 500,000 node update in about 2.3 seconds on an older 2.5-(3) GHz Intel Core i7… So I think what your doing should be pretty easy.

Oh and yes… I forgot the Fast Recast updating is still on the beta client :confused:

Thanks Burdock,

My deploy is IOS so I’ll do some test to see what I can get away with, but I’m excited to test things out. I’ll be picking up pro shortly and may still try out recast graph if I can get a hold of the beta!

Thats good to hear! keep me posted on your game, sounds interesting :slight_smile:

I think you will be happy with A* pro, the RVO(Local avoidance) is just plain great! And with things like square sliced recast graphs in the pipeline, you will have plenty of options to work with :slight_smile:

Though I still think well made grid graphs will be your best option!