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.

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]

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?

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   }}

Right, gotcha. Got myself a bit confused there thinking about something the wrong way around. Cheers for the help.

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?

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.

I have a node class. Yeah, i can add a vector of neighbours alright. cheers