next »

[nikki]

i've been experimenting with 3d grid based pathfinfing (think dwarf fortress)

but because of the ^3, memory usage adds up amazingly fast, now i'm at a 512x512x64 map and it's using >500 Mb already.

(i'd love to reach 800x800x200, but my computer doesn't even go there)

i am aware i still use a rather naive/full-on/unoptimized approach, but i wouldn't know a way of optimizing this .

anybody out here got some pointers/links/tips/knowlegde ?
thanks in advance
 

[JakobProgsch]

A* should also be able to work on implicit grids/graphs. So depending on what the "base data" is you might not need to actually build the grid. Another approach might be to only store the walkable areas in a sparse structure/graph. That is obviously not much of a gain if almost everything is walkable.

[Danmark]

I don't understand how your memory usage got so high on that map, even for naive pathfinding.

Can your characters fly, walk on walls, only walk on the ground and change levels at certain places, or what? What's the environment like? What technique are you using exactly? Are you sure there are no glaring bugs in your implementation?

Look up Hierarchical A*.

[BorisTheBrave]

Sounds like you are using 4 bytes per tile, not an unreasonably amount. But it can be improved. If all you need is if each tile is full/empty, then you only need one bit per tile, a saving factor of 32 (the edges from each tile are implicit, like Jakob says).

[nikki]

thanks for all the tips already guys, some more info:

the a* code I use is a piece of code written by someone else, and I changed all 2d maps into 3d maps.

(and since i'm still playing arounf the actual pathfinding atm is only at the first 3d index)

the base data, is not really known in advance because the player can change the terrain, however I would say that usually a lot of space will not be walkable (either underground or in the air) , having said that I would like to add some flying creatures eventually.. (but maybe they should be using other techniques)

another point is that the original code was build for large groups of characters, (with logic to avoid collision, look for temporary unavailable paths (because of other units))

oh wait i could show this to be hopefully clearer:

Code:

Field walkability :Byte[,,],.. 'array that holds wall/obstacle information
openList :Int[ ],.. 'array holding ID# of open list items
whichList :Int[,,] 'array used To record
Field openX :Short[ ],.. 'array stores the x location of an item on the open list
openZ :Short[ ],.. 'array stores the y location of an item on the open list
parentX :Short[,,],.. 'array To store parent of each cell (x)
parentZ :Short[,,],.. 'array To store parent of each cell (z)
Fcost :Byte[ ],.. 'array To store F cost of a cell on the open list
Gcost :Byte[,,],.. 'array To store G cost For each cell.
Hcost :Byte[ ],.. 'array To store H cost of a cell on the open list
tempUnwalkability :Int[,,],.. 'array that holds info about adjacent units
nearBzPath :Short[,,],..
claimedNode :TUnit[,,],.. ' array that stores claimed nodes
gGroupUnit :TUnit[],.. 'used To sort a selected group of units
island :Int[,],..
gDiagonalBlockage :Int,..
gPathCost :Int,..
unitList :TList,..
onClosedList :Int,..
useDijkstras :Int

and this is how and how big they are initialized:

Method Init(tw:Int, th:Int, mw:Int, md:Int)

      tileWidth         = tw
      tileDepth         = th
      tileSize         = TileWidth
      mapWidth         = mw
      mapDepth         = md
      walkability       = New Byte[mapHeight,mapWidth,mapDepth]          
      openList          = New Int[mapHeight*mapWidth*mapDepth]       
      whichList       = New Int[mapHeight,mapWidth,mapDepth]      
      openX         = New Short[mapHeight*mapWidth*mapDepth]      
      openZ         = New Short[mapHeight*mapWidth*mapDepth]      
      parentX         = New Short[mapHeight,mapWidth,mapDepth]      
      parentZ         = New Short[mapHeight,mapWidth,mapDepth]      
      Fcost         = New Byte[mapHeight*mapWidth*mapDepth]      
      Gcost         = New Byte[mapHeight,mapWidth,mapDepth]      
      Hcost         = New Byte[mapHeight*mapWidth*mapDepth]            
      tempUnwalkability    = New Int[mapHeight,mapWidth,mapDepth]    
      nearBzPath      = New Short[mapHeight,mapWidth,mapDepth]       
      claimedNode      = New TUnit[mapHeight,mapWidth,mapDepth]   
      gGroupUnit      = New TUnit[1]       
      island         = New Int[mapWidth,mapDepth]
      unitList         = New TList   
      onClosedList      = 10    
      useDijkstras       = False

   End Method

as you can see most of the cost come from : tempUnwalkability, openList, whichList..
i stop typing now, (i fell off a racingcycle and hurt my wrist badly, i'm in pain..)

ps

Look up Hierarchical A*.

i did, it sounds like a solution but i only managed to find 2 academic pdf's (without pseudo code) and many video's without (pseudo)code , have you got a link or something perhaps ?
    

[BorisTheBrave]

Yes, so you have a lot of arrays that are the same size as the map, for convenience. But they'd don't really need to be like that, as you only need data to cover the "open-set" at any one time. You could replace the arrays with hashmaps, and make sure you delete data when you don't need it (this would be a *sparse* data structure mentioned earlier).

However, it's probably a lot of effort if you don't really understand the algorithm well. You might prefer just to live with the memory usage.

[nikki]

You might prefer just to live with the memory usage.

can't do! Instead i googled slightly better on 'Hierarchical A*' and found these :
http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html
http://gamedev.stackexchange.com/questions/31208/how-can-i-generate-a-2d-navigation-mesh-in-a-dynamic-environment-at-runtime
http://aigamedev.com/open/tutorial/symmetry-in-pathfinding/
and
http://aigamedev.com/open/review/near-optimal-hierarchical-pathfinding/


i'll be back 

[QuaziGNRLnose]

an octree implementation might help in saving a hell of a lot of memory

[Laurent C]

I am making a game similar to yours. My map is 1024x512x1024 and memory usage is at 150mb total. I use chunks of 16x16x16 that will not use any memory when they are empty (all air blocks). Each chunk can use a different data format for compressed data but that's WIP.

I have no idea why you're using so many arrays. Some of them seem useless or too big.

Are you making a voxel RTS?

[nikki]

@Laurent C : Yeah, thse arrays are because of a* pathfinding for large groups (with a binary heap), and the memory usage is excessive because i naively just took a gridbased 2d astar, and plonked another dimension on top of that.. The saving/keeping in memory of a much larger (chunk/region/compressed) 3d world is not really the problem) , unless your talking 150mb for map and pathfinding a large group offcourse! then i'm very inrrested

@QuaziGNRLnose and ^^ : Yep, i suppose i'll have to start making smarther graphs instead of just using the individual 3d tiles as nodes.

atleast i am pretty sure now it's no premature optimalization  

[st33d]

A technique I'm currently using for a map that constantly changes is to have an empty graph that is overlaid on to the world map.

Think of it like having a sheet of acetate with a grid on. You then overlay that on to the world with the start of the search being the center of the sheet.

You then calculate the path from the center, checking if nodes on the sheet would be blocked - relative to where you laid the sheet on to the map.

This is slightly more expensive because you have to compare relative positions all the time. But you save a great deal of memory in the process.

If you reach the edge of the sheet you simply consider it a sub-optimal path. It should be good enough for enemy AI.

[nikki]

slowly a strategy is forming in my head..

i think i'll be trying to implement stacked pseudo quadtree (I've made that up)
because of the possibilty of changing the terrain i feel a true quadtree might become complex/heavy in updating and dynamically changing the graph (because you never know how big the area was before and after (so the maximum of new to ad children could become very big)) so i'm leaning towards a solution where

-a maximum area of a graph is 16x16 (i'll go 3d later)
-when nonwalkable tiles are within that space i'll split it up in smaller unobstructed rectangles (when the smaller area is bigger then a certain value, otherwise i'll leave them as single sized rectangles/tiles)

things i don't get yet
-how to efficiently save connections
-how to divide an area the fastest into smaller unobstructed rectangles
-how to connect said rectangles to all their neighbour (over all possible side locations)

[nikki]

-how to divide an area the fastest into smaller unobstructed rectangles

put visually: how to get from the left image to the right ?
i found academic term on this : rectangular decomposition, but i don't understand the crazy math in those papers, and i can't find a more practical gamedev orientated example

[st33d]

Err, that's bin-packing, which is a subject in itself and isn't QuadTrees.

QuadTrees, or OctTrees (which I think is what you're planning on doing) optimise volumes by breaking them up into squares. Breaking them up into arbitrary rectangles doesn't help at all because you don't have a consistent standard for diving into higher resolutions. You can't just pick a location and instantly know what depth you have to go to with arbitrary rectangles, you'd have to stop at every level and measure everything.

[nikki]

well i want to try the big idea at : http://users.cecs.anu.edu.au/~dharabor/data/posters/harabor10-cecsposter.pdf to begin with and for that algorithm to work i need to divide in rectangular rooms..

[st33d]

That's HSA*

You break up the map into a lower resolution and connect at the significant entry and exit points.

I remember though that you said you wanted to be able to change the terrain, so breaking it up into rectangles isn't much help.

It doesn't have to be rectangles either - just any kind of low resolution representation of the map.

[nikki]

atleast i generated right from left atm

I remember though that you said you wanted to be able to change the terrain, so breaking it up into rectangles isn't much help.

I figured (but i know nothing about pathfinding, so i'm probably wrong) that in the above case i always know a start resolution for any goal point (16x16) and look from that resolution to more precise rectangles..

[nikki]

QuadTrees, or OctTrees (which I think is what you're planning on doing)

an octree implementation might help

So I started with a quadtree (1 dimension at a time  )
I was wondering though :
After you've created the nested nodes and leaves of the tree, how do you handle actually traversing the tree ?
I can see how every node shares a certain (super)parent but how do you handle the question what neighbours to check, and how deep, and what neighbours don't collide and are of  the same value ?

is it a lot of bresenham and realtime calculations or are there more elegant ways ?

[st33d]

A quad tree will generally sub-divide after a certain threshold of content in a quad. You have to dive up and down through the nodes to add up stuff. It's only optimal for large and small items in the mix because of all the mandatory diving.

[nikki]

well I can definitely see how this will improve the memory usage especially in 3d octree, so I guess my original problem is solved  , however It still doesn't look great (and uses quite some nodes typically >100000 for a forested and blocks map at 1024x1024)
and i found something that might be good too; "jump point search" as http://www.bay12forums.com/smf/index.php?topic=92732.0 and http://qiao.github.com/PathFinding.js/visual/

That's HSA*

that also seems very good to try!

lots to try