next »

[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

[PompiPompi]

Is it possible to simply compile your game to 64 bits? XD

[Laurent C]

Is it possible to simply compile your game to 64 bits? XD

He's clearly using too much ram and I doubt 64 bits will help. I am making a similar game and my pathfinder works fine with just 16 bits for now.

[PompiPompi]

16 bits? O_O
Well it really depends what he\she is doing. If it is possible to compress the weight map, if it is possible to make assumptions on the A* process itself.
64 bit is a viable solution. Of course it make less sense for certain games than others.
If you are workign on a 2D platformer it's a bit awkward to demand 8GB of memory.
If it is a minecraft like game, then it make sense.

[dougbinks]

You might want to take a look at Mikko's Recast and Detour (http://code.google.com/p/recastnavigation/ ) for some inspiration. Recast was designed for polygon mesh to navigation mesh conversion, but it uses a voxel like approach to create the navmesh.

[powly]

I hope I'm missing something here, or why don't you just use a linked list of all open/closed nodes and only push adjacent nodes into the list? That sholdn't grow too big if you don't have a huge 3D maze, in which case you'll end up using lots of memory anyway.