Sign in to follow this  
discodowney

Distribution of Nodes for A*

Recommended Posts

discodowney    102
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 this post


Link to post
Share on other sites
alexjc    457
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 this post


Link to post
Share on other sites
alexjc    457
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 this post


Link to post
Share on other sites
discodowney    102
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 this post


Link to post
Share on other sites
Emergent    982
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...)

Share this post


Link to post
Share on other sites
Sneftel    1788
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.

Share this post


Link to post
Share on other sites
discodowney    102
Okay so ive been looking up adjacency lists.

My map is approx 100 x 100. so if i have a node at every 1.5 thats gonna be a list thousands of lines long that has to be hardcoded. That is gonna be a killer. think ill increase the distance of the distribution.

Share this post


Link to post
Share on other sites
Emergent    982
Quote:
Original post by discodowney
My map is approx 100 x 100. so if i have a node at every 1.5 thats gonna be a list thousands of lines long that has to be hardcoded.


Huh? You write code that automates this process for you; you don't hard-code it...

Quote:
What do you mean offset geometry?


This is the geometry you get after you "push out" your level geometry everywhere along the normal by a distance 'r.'

Say you've got an agent which for collision purposes you model as a sphere of radius 'r.' Instead of worrying about intersecting this sphere with your level geometry, you can instead treat your agent as a point and test for collision against offset geometry.

Here, a picture is worth a thousand words:

(taken from here)

Here the blue-green polygon represents your level geometry, and the black curve represents your offset geometry. The distance between them would be the radius of your agent.

[Edited by - Emergent on April 5, 2010 8:18:18 AM]

Share this post


Link to post
Share on other sites
discodowney    102
Quote:
Original post by Emergent
Quote:
Original post by discodowney
My map is approx 100 x 100. so if i have a node at every 1.5 thats gonna be a list thousands of lines long that has to be hardcoded.


Huh? You write code that automates this process for you; you don't hard-code it...



Maybe im being really stupid here but its this part im not sure about.

If i have a node, node 7

1 2 3
6 7 8
11 12 13

How can i automate the process of telling it that, for eg., 7 is connected to 1,2,8,11,13 but not the others?

Share this post


Link to post
Share on other sites
Emergent    982
Quote:
Original post by discodowney
How can i automate the process of telling it that, for eg., 7 is connected to 1,2,8,11,13 but not the others?


That's the point of the line segment vs. level-geometry or offset-geometry tests.

Simplest version (pseudocode):


Start with empty adjacency list.

For each pair of nodes (p,q)
{
if(segment from p to q does not intersect geometry)
{
add an edge from p to q to your adjacency list
}
}

Share this post


Link to post
Share on other sites
discodowney    102
A question about storing the adjacency list. Say i compute my adjacency list and it is something like

1 -> 2,3,6,7
2 -> 1,5,7
3 -> 1,2,6
4 -> 5
5 -> 2,4
6 -> 1,3
7 -> 1,2

What is the best thing to use to store the data. a 2D vector?

Share this post


Link to post
Share on other sites
Emergent    982
Quote:
Original post by discodowney
What is the best thing to use to store the data. a 2D vector?


Often one represents each node as a class/struct, one of whose elements is a list or vector of pointers to other nodes. E.g.,


struct node
{
vector2d position;
std::vector< node* > neighbors;
};

std::vector< node > graph;


This is perhaps a little oversimplified though; it's probably best to actually wrap everything up nicely in a class with accessors which hide the internal representation.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this