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.
Distribution of Nodes for A*
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]
Author
Quote:Original post by EmergentQuote: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?
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 }}
Author
Right, gotcha. Got myself a bit confused there thinking about something the wrong way around. Cheers for the help.
Author
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?
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?
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement