Jump to content
  • Advertisement
Sign in to follow this  
discodowney

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.

If you intended to correct an error in the post then please contact us.

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


Link to post
Share on other sites
Advertisement
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
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
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
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
Yeah the problem is with determining which nodes are neighbours. grand, adjacency matrix it is.

What do you mean offset geometry?

Share this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!