Hello,
I am in the process of incorporating some A* path finding into a couple of NPC's, and I have a question.
Originally I was planning on generating "nodes", which consist of just an invisible block, that is placed on the ground. I can then ready of each block is within an object or not, and the algorithm can run. The end product will consist of the nodes, in order, which will dictate the path.
After thinking about this a bit more, generating a grid of 100x100 nodes, would be 10,000 objects, so I'm starting to think this is too many and will overload the game engine?
Do you guys have any other ideas I can try to incorporate this algorithm? Basically all I need is an array, and I need to be able to have a couple variables accociated with each element (e.g. a couple variables to rate the block, as well as being able to determine if the element is inside something or not.) Any help is appreciated, thanks!

For a pathfinding like this, define your nodes as structs.

Example:


This node holds a position, how many nodes are connected to it, and a pointer to an allocated array which includes pointers pointing to the connected nodes.

if you need to visualize your nodegraph, lookup for the draw_ methods in the manual.

If you use real entities, you'll end up consuming to much memory(and might get a message for to much entities anyway)

PS: the above is just a simple example, try to find the best way for you

Greetings
Rackscha

You should look into this tutorial for the basics:
http://www.opserver.de/coni_users/web_users/pirvu/au/tutorials/zipped/astar_en.zip

After that consider the usage of structs (Look at Rakschas post and manual) for your data and you might also have a look at this:
http://aigamedev.com/open/tutorial/symmetry-in-pathfinding/

Hm, a rough estimation for a 100x100 grid of freeplaced nodes:

10.000 * 14 bytes = 140 kilobytes
...should be enough.
Most good computers can handle that amount of data nowerdays.

(with x,y,z each 4 bytes, and 2 bytes for metainformation)

Hi,
if you choose to use arrays, here is an example what you need for A*.
I used it and works fine. Usually A* data is stored in ordered linked list, but static array is faster. Not only my opinion, check this: http://www.gamasutra.com/view/feature/3096/toward_more_realistic_pathfinding.php?page=2
Moreover, this solution is very handy for error search. Everything can be represented, I used sprites, but it is slow if all the node values are displayed.

char DataArray[MAPX][MAPY]; // to store tile/node values of accessibility and move cost values

// A* open and closed lists
var astar_clist[MAPX][MAPY];
var astar_olist[MAPX][MAPY];
// values needed for distance estimation and tracking
var astar_F[MAPX][MAPY];
var astar_G[MAPX][MAPY];
var astar_H[MAPX][MAPY];
// storing previous path element of each node
char astar_parent_x[MAPX][MAPY];
char astar_parent_y[MAPX][MAPY];
// = 220000 bytes if 100x100

// the resulting path array holding x;y coordinate values of path steps
char pathX[MAXPATHLENGTH];
char pathY[MAXPATHLENGTH];
// path directions in each step
char pathDir[MAXPATHLENGTH];

@Damocles_: i need a bit help for your description. You wrote 2 bytes for metadata. Which metedata can you store in 2 bytes if using a nodesystem?

Or the poster should specify if he/she is using a gridbased system with constant placement or a freely nodebased system.(the later requires a bit more than 2 bytes of metadata)

Well it was an example to show that the required memory is far from huge.

it really depends on how this nodegrid is set up.

lets assume a more or less even nodegrid (more like in an RTS), but where each node can have some positionoffset to adapt it to local conditions.

for the offset 2 bytes (short) are enough, where it says what the offset is to the "normal" gridposition
x,y together 4 bytes
for the height 3 bytes are excact enough, unless you make a scientific simulation
z 3 bytes
---------
Metadata
---------
byte #1 : type of node , where each bit indicates a parameter:
Flags:
1-> is passable,
2-> only narrow chars,
3-> is a locked door,
4-> is in water
etc...

-------------
byte #2: the link flags to the other nodes, (when using my even grid idea) -> if a passble link from my node to the other node is there or not.
to store 8 connection you only need 8 bits then, aligned like this (N=my node)

1 2 3
4 N 5
6 7 8

----------------

altogether 9 bytes per node ...

--------

ok this is a bit chrunched (on a mobile phone this makes more sense than on a PC), but also an example how to compress the data to save memory.

but 20 bytes per node should be good also.

Well, if you're talking about such a system i would call it gridbased, and not nodebased. i know the term nodebased only for free defined systems without any placing pattern. And maybe for this system, it should be possible to avoid the offsets aswell.(or dou you have a usecase for this?)

(Well nodes are firstly points in a graph.)

I assume that from the "100x100" node question.
And in fact, such a system makes sense when:

-the passabality area is 2D, -> has no "bridges/intersections"
-it needs to have a fast system of generating the grid (much like in an RTS with custom maps)
-there are obstacles, but you dont want to alsways leave out a complete grid just because there is the tip of a tree nearby
(therefore the offsetdata to move the nodes within certain bounds)

So I would say this fits well to top-down tactcal games, or diablo type games.

a system with free-placable nodes I would structure like this

9 bytes x,y,z position data
2 bytes Metadata (whatever Info flags, such as passability, content etc)
1 byte num of connected nodes
(0 .. n times) 2 byte node id of other node

-> this would be the storage format.
in the actual memory I would limit the number of linked nodes to like 16 and then just store
this into 32 byte linkdata per node (where id 0 indicated no link)

There are probably some ways to save memory, but its a reasonable idea, and fast to access.

as you see I'm using the google translator because my English is not aq very good.

q other concern I have is utilizadola Well I find 2D path function for a program called gemix and div, I have seen examples of path find work here but not in the 3D devidamente, is my concern is whether it is possible to find a path in 3d or 2d only be?


thanks for the help