Any grid update strategies for a procedurally generated landscape?

Hi

I wonder how to update a grid in a procedurally generated landscape project. What is the most efficient way?

Just imagine a voxel-like game like Minecraft or a non-voxel game like (our) Proven Lands: here (with hills, mountains, cayons, a lot of obstacles and magic)

Requirements

  • terrain is procedurally generated
  • endless and seamless terrains, landscapes and movement
  • a lot of small to medium sized obstacles and enemies
  • no delays or freezing allowed
  • on mobile?

So far, I do this

  • generate terrain (256x256 per terrain)
  • place enemies and obstacles
  • generate a GridGraph for each terrain, and save it
  • load GridGraph of the current terrain
  • if you change the terrain: load the new GridGraph
  • which leads to: a tiny delay (which is ugly!)

I tried a few other ways, like

  • generate a grid of 3x3 GridGraphs (32x32 each)
  • player is always in the center
  • if he leaves a grid, you generate the missing one
  • which led to: a super tiny delay

Is there a better way? Any ideas?

The best way is to do a lot of custom stuff.

Have a single grid graph, the player is in the centre.
When the player has moved to some distance X from the centre of the graph, you move the grid graph. But you don’t want to recalculate everything, that would be wasteful.
Instead you move the actual nodes in the grid, discard some that happen to end up outside the grid, and recalculate new ones that you haven’t seen before.

123456789 123456789 123456789 123456789 123456789
Each digit corresponds to a node.

Move 3 units to the right

456789123 456789123 456789123 456789123 456789123
The 1,2 and 3 nodes have wrapped around (to avoid creating new ones), all those nodes should be completely recalculated since they currently have invalid data from the other side of the graph. Also the 4s and 9s need to be recalculated since their neighbours have changed.

Moving the nodes in the graph can be done with a simple loop.
GridGraph gg = ... int xoffset = 3; // assuming 0 <= xoffset GridNode[] tmp = new GridNode[gg.width]; // This should be cached for ( int z=0;z<gg.depth;z++) { for ( int x=0;x<gg.width;x++) { tmp[x] = gg.nodes[z*gg.width + x]; } for ( int x=0;x<gg.width;x++) { tmp[(x+xoffset)%gg.width] = tmp[x]; // Set the index of the node, required for correct pathfinding tmp[x].nodeInGridIndex = z*gg.width + ((x+xoffset)%gg.width); } }
Then you would have to recalculate all nodes in the new region as well as those ending up on the edge of the grid or being moved from the edge of the grid (the 4s and 9s in the example).

Hey. Thank you a lot for this super quick solution. I’ll give it a try. And in case you’ve too much spare time or you don’t sleep ;), if it’s not too time consuming, could you just add such an example to the general unity package? For comparison. Like: player object runs on a huge procedurally generated terrain

Aron, this looks like exactly how I want to do this, but I can’t figure out how to edit the GridGraph that I created in the editor. Is there documentation on that?

Hi

I have built an example scene for it now.
It uses basically the same technique as illustrated above, but also handles all weird special cases.

Here is a webplayer demo: http://arongranberg.com/astar/webplayer?p=procedural
The graph is 200*200 and updated when the agent goes 10 world units ( about 14 nodes ) away from the center of the graph. On my computer it is running at constantly above 140 fps, usually higher. It does sometimes drop down to 40 for a frame or so, but that is because of static batching which I do for the procedurally generated tiles, not because of the pathfinding stuff.

PS: editing a grid graph can be done via
GridGraph gg = AstarPath.active.astarData.gridGraph; // do stuff AstarPath.active.Scan ();

Awesome! I’ll try it out. Thank you Aron, I really appreciate this.

The new example scene is now in the Unity 4.3 beta ( A* Pathfinding Project 3.3.11 ).
See http://arongranberg.com/astar/download#

1 Like

I finally got back into this, and the supplied code is fantastic. Now if only I could get it working for LayerGridGraphs :stuck_out_tongue:

Looks like im running into the same issue you are with LayerGridGraph. I just made a new topic before finding this one.