# Distribution of Nodes for A*

This topic is 3029 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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'.

##### Share on other sites
A 2D grid would do fine. Pick a resolution that's 50% of your minimum actor width, so you can plan through tight spots.

If you use waypoints, 1m-2m is good for pathfinding and reasoning, but if you're short of memory use a coarser resolution.

##### Share on other sites
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.

##### Share on other sites
It's best to pick the size of an actor roughly independent of the actual 3D mesh, just decide what it should be from a gameplay perspective and work with that. That way if you make minor changes to the model in the future it shouldn't break anything.

##### Share on other sites
Instead of treating nodes as points, you can always treat nodes as regions, as in the navmesh approach.

##### Share on other sites
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.

##### Share on other sites
Quote:
 Original post by discodowneyIve 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 discodowneyHave 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...)

##### Share on other sites
Yeah the problem is with determining which nodes are neighbours. grand, adjacency matrix it is.

What do you mean offset geometry?

##### Share on other sites
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.

1. 1
2. 2
3. 3
Rutin
22
4. 4
JoeJ
16
5. 5

• 14
• 29
• 13
• 11
• 11
• ### Forum Statistics

• Total Topics
631774
• Total Posts
3002287
×