Updating a specific portion of the graph when placing a building

Beginner Questions
1

Hello again! I have another question about your amazing project. As far as AI goes, i’ve been able to run it perfectly for myself with great performance. Now, the thing that i’dlike to know about is graph updating.

Making a TD game and i’m currently only giving the player the ability to build when the round ends (no enemies). And when the round beginds I update/rescan the graph to take in account the new buildings. This works well for what I need, but let’s say I want to build buildings and update the graph WHEN the new building is placed and also update the AI. Is this possible? Not just for this kind of project, but lets say for RTS games in general, when the pathing has to be updated for every new building placed. Iit possible with your pathfinding project?

2

Sorry, I have another question. More again, about optimization and your opinion on it. So lets say I have an RTS game with a fairly large map. Would it be possible to have many grid graphs, rather than 1 small one? So I only recalculate the graph(s) that intersected the newly built building?

3

Hi

You can use graph updating during runtime (see the code section): http://arongranberg.com/astar/docs_dev/graph-updates.php
This will only recalculate the nodes that are inside the bounds object (well, it does need to run a single pass through all the nodes in the graph, but usually that is pretty fast).

4

But what performance hit would it be? Especially when the map is big (warcraft 3 map sizes, for example). As far as I understand it would still require to update the whole grid graph? Would it be possible to use multiple grid graphs, and update only the ones that had an object placed on them?

How are these kind of things handled in most strategy games or how would you recommend approaching it?

5

I was wondering the same thing. I wanted to see if miniature graphs could be made for the buildings but I was worried about memory.

6

HI

No, it will only recalculate the nodes that are inside the bounds.
It will do a single pass over all the nodes in the graph, but it is a very tight loop so usually it is not a problem.
Try it out and see if it works for you.

Adding more graphs does not make a difference, it needs to traverse all nodes in all graphs.