Can people who have done A* please let me know how ye decided upon the distribution of the nodes aaround hte map? We have our map, and i have coded up an A* algorithm. Im just not sure what the beest way to distribute the nodes is. The map can only be traveresed over the x and z axis'.

So if my actor, we dont have the models yet so dont know, is width 3, make it a node every 1.5, in a grid. cool. cheers.

Instead of treating nodes as points, you can always treat nodes as regions, as in the navmesh approach.

Ive already done a good bit on the use of nodes, and they will suit the purposes of this game. I was looking at nav meshes a while back and said id have a go if i had time. Doesnt look like i will.

Have bit of a problem. I was trying to add the nodes with an algorithm. So every 1.5 (for now) in the x and z a node is added in grid form, as above. Then id check for intesections with enviornment objects. But Im not sure how i go about defining which nodes are neighbours. I dont get how i create a node and then say set which ones its connected to.

Initially I was considering using an adjacency matrix, so just a list of 1's and 0's id make myself. Where there was a 1 there would be a connection with a node and a 0 no connection. This is obviously level dependant then.

which is the best. Actually right now id prob need the quickest.

Quote:Original post by discodowney
Ive already done a good bit on the use of nodes, and they will suit the purposes of this game. I was looking at nav meshes a while back and said id have a go if i had time. Doesnt look like i will.

Ok.

Quote:Original post by discodowney
Have bit of a problem. I was trying to add the nodes with an algorithm. So every 1.5 (for now) in the x and z a node is added in grid form, as above. Then id check for intesections with enviornment objects. But Im not sure how i go about defining which nodes are neighbours. I dont get how i create a node and then say set which ones its connected to.

Initially I was considering using an adjacency matrix, so just a list of 1's and 0's id make myself. Where there was a 1 there would be a connection with a node and a 0 no connection. This is obviously level dependant then.

which is the best. Actually right now id prob need the quickest.

Is the problem with representing your graph, or is it with determining which nodes are neighbors in the graph?

Ordinarily you'd precompute the adjacency information for your nodes and store them in your map file. Here you just use whatever representation of a graph you like best; this boils down to either (1) an adjacency matrix, or (2) an edge list.

To determine adjacency is slightly trickier, and depends on your needs, but it basically comes down to the idea that an agent can always walk in a straight line between points.* Under this assumption, if your agent were a point particle, you'd just connect nodes whenever the line segment between them does not intersect the level geometry. Since your agents are not point particles but take up space, you probably actually want to test these segments not against your level geometry directly, but against offset geometry.

*(Can agents always walk between points when they're connected by a straight line? This is presumably always true for your case, but in general it may not be: Consider an airplane (which can never slow down too much) with bounded turning radius...)

Yeah the problem is with determining which nodes are neighbours. grand, adjacency matrix it is.

What do you mean offset geometry?

A (dense) adjacency matrix representation is a terrible approach for a graph you'll use for pathing. If your world has 1000000 nodes, do you really want to have to look through 1000000 entries every time you need to find the four neighbors of one single node? For that matter, do you want to use 1000000000000 entries to store the thing?

Everyone uses adjacency lists. Go with that.

Ill read up on adjacency lists so. Cheers