Hi there, What I''m doing, is making a 2D Point-and-Click game (like the old Lucasarts Games). I''m in the process of starting the path-finding algorithm. I have the areas that I want to path-find through ''marked out'' as polygons (in Java, btw). Next, I want to use some method of finding out which other polygons each polygon ''touches''. This is so I don''t have to use A* on a huge polygon, but instead a small one. I hope you understand what I mean. Thanks Stewart Holmes It''''s over for now... until yesterday begins again... tomorrow... tomorrow... tomorrow... [Powerman 5000 - Watch the Sky for Me]

There was a similar topic a couple weeks back that may be helpful
http://www.gamedev.net/community/forums/topic.asp?topic_id=90466

quote: Original post by ServantOfGlaaki
Next, I want to use some method of finding out which other polygons each polygon ''touches''.

Presumably these polygons are generated randomly at run time??? If not, then you can write down a connectivity map during development and work out optimal paths between any two polygons and store this as a list.

Assuming you need to work out connectivity at run time, then it would be helpful to know how you are defining each polygon. Presumably a list of edges? You might find it beneficial to produce (during construction of the map) a list of edges and which polygons they belong to. Then it is a simple matter of traversing the list to create a second list of polygons that share a common border, which is your connectivity map you will need for many of the pathfinding algorithms.


Cheers,

Timkin

quote:
Presumably these polygons are generated randomly at run time??? If not, then you can write down a connectivity map during development and work out optimal paths between any two polygons and store this as a list.

What I intended to do, was to work out a connectivity map at run-time, but I just realised that I could figure it out after the polygons are defined, before run-time (and store it in a text/XML file to be loaded at run-time).

quote:
Assuming you need to work out connectivity at run time, then it would be helpful to know how you are defining each polygon. Presumably a list of edges? You might find it beneficial to produce (during construction of the map) a list of edges and which polygons they belong to.

Currently, I am using Polygon objects for my polygons (I''m using Java); the object stores the points of the vertices. By storing the edges, would I just convert the polygon into a group of lines with 2 points?

quote:
Then it is a simple matter of traversing the list to create a second list of polygons that share a common border, which is your connectivity map you will need for many of the pathfinding algorithms.

You''ve lost me a bit on this one. By a ''list of polygons that share a common border'', I''m really not sure what you mean. Could you explain to me exactly what a connectivity map is?

Thanks for your help so far
Stewart

It''''s over for now... until yesterday begins again... tomorrow... tomorrow... tomorrow...

[Powerman 5000 - Watch the Sky for Me]

quote: Original post by ServantOfGlaaki
What I intended to do, was to work out a connectivity map at run-time, but I just realised that I could figure it out after the polygons are defined, before run-time (and store it in a text/XML file to be loaded at run-time).

So in the worst case scenario it could be done by hand. We can do better than that though...

quote: Original post by ServantOfGlaaki
the object stores the points of the vertices.

Not the best scenario, but not impossible to deal with.

Let's define a new object (sorry, I'm using C since I don't code in Java... you can translate )

struct border_type{  double endPts[2];  int    neighbour[2];};typedef border_type borderType; 

You would probably need to declare an array of these borderType ojects to hold your all of the maps border information. You can work out a reasonable maximum number of border types by adding up the number of sides of all polygons... or you could declare it dynamically.

Now for each polygon, create a border element, fill in the end points and the first neighbour variable. For the second neighbour variable, set it to a value that means wall. Once this is done, run through the list and compare the end points of border elements. Where two border elements have the same endpoints, they should have the same neighbours. Delete the copy of the object.

Now you have a list that contains all border elements in your map. You should now create a second, more efficient list, that lists for each polygon all of its neighbours; call it a neighbour list maybe. You can do this by looking up all instances of a polygon in the border list... the other neighbour variable defines the next polygons that can be reached from the subject polygon.

Since this is being done offline dont be overly worried about the time to create each of these lists. Once you have the neighbour list, pathfinding will be far and far more efficient.

There are quite possilby more efficient methods to compute this connectivity information... this is just one idea. I hope it helps.

Cheers,

Timkin

[edited by - Timkin on May 5, 2002 11:22:19 PM]

Thanks again Timkin. I''ve been a bit busy the last few days, but here I am, asking questions again ;-).

//You would probably need to declare an array of these
//borderType ojects to hold your all of the maps border
//information. You can work out a reasonable maximum number of
//border types by adding up the number of sides of all
//polygons... or you could declare it dynamically.

By border, do you mean the same as an edge of the polygon? If so, am I correct in assuming that first I would feed all the sides of all my polygons into an array of border objects?

//Now for each polygon, create a border element, fill in the
//end points and the first neighbour variable. For the second
//neighbour variable, set it to a value that means wall. Once
//this is done, run through the list and compare the end points
//of border elements. Where two border elements have the same
//endpoints, they should have the same neighbours. Delete the
//copy of the object.

What does the neighbour keep track of, exactly? How do I fill in the first neighbour variable? Why do I need to set the other neighbour to wall? I really don''t understand this section, sorry.

If it''s any help, I can try to explain my problem again. Consider the following image (stolen from DOTT):



The white quadrilaterals you can see are the shapes I want to use in the connectivity map.

Would it be any easier if I used triangles instead of quadrilaterals? It shouldn''t be hard to triangulate the polygons, and then work with them.

Thanks again
Stewart Holmes

It''''s over for now... until yesterday begins again... tomorrow... tomorrow... tomorrow...

[Powerman 5000 - Watch the Sky for Me]

quote: Original post by ServantOfGlaaki
By border, do you mean the same as an edge of the polygon? If so, am I correct in assuming that first I would feed all the sides of all my polygons into an array of border objects?

Yes. At least that's the easiest way to do it without extra book-keeping of which edges you've processed. Here's an algorithm for you:

For each polygon    For each edge       create border object       initialise border object to current edge  

(As I said earlier, you might want to create a static array of border objects).

Here's a C function for initialising the border data object. It takes as arguments a pointer to the BorderType object just created, the current polygon id and the two end points. Obviously if you were allocating memory for the BorderType objects at run time, you could create a constructor function that did this for you and initialised the object to the values passed to the constructor.

Here's a new version of the border_type object too... the typedef should be the same...

struct border_type{   double endPts[2][3];/* number of pts x number of dimensions*/     int    neighbour[2];};void InitialiseBorderElement(BorderType* pBorder, int PolygonNum, double* endPtA, double* endPtB){pBorder->neighbour[0] = PolygonNum;/* there are other more efficient ways to copy *//* the arrays... but Im doing the following for clarity */pBorder->endPt[0][0] = endPtA[0];pBorder->endPt[0][1] = endPtA[1];pBorder->endPt[0][2] = endPtA[2];pBorder->endPt[1][0]) = endPtB[0];pBorder->endPt[1][1]) = endPtB[1];pBorder->endPt[1][2]) = endPtB[2];}  

quote: Original post by ServantOfGlaaki
What does the neighbour keep track of, exactly? How do I fill in the first neighbour variable? Why do I need to set the other neighbour to wall? I really don't understand this section, sorry.

Hopefully the above code helps to highlight things a little better.

The neighbour variable keeps track of the polygon ids for the polygons either side of the border segment. A line has only two sides so we need only to store only two values. The indexes will be used later for the pathfinding. When you create a border element for a particular polygon, just initialise the first neighbour to be that polygon. You set the other to be a wall because later, once you've done a bit more processing on the list of border objects, the neighbours that are still set to wall represent the outer boundary of your polygon map... i.e., regions where you cannot go to.

Once you've created a border object for every edge, then you will obviously have doubles... consider the following very simple example of two rectangles bordering each other...

D----Q----C|    |    || 1  | 2  ||    |    ||    |    |A----P----B  

After running through the above algorithm, your border list would contain objects for each of the following lines:

AP,PQ,QD,DA,PB,BC,CQ,QP

Clearly the border elements PQ and QP are the same line. They can be identified as identical because their end points will be identical. Make sure when doing this check though you think about the orientation of the end points and the order in which they were stored. To take care of this double-up... make a note of the polygon neighbour mentioned in the object for QP (in this case the polygon ID is 2) and simply delete the QP object. Then, in the PQ object, set the second neighbour variable to 2, the polygon ID of polygon 1's neighbour that lies on the other side of the line PQ.

Make sense? I hope it does!

Check every border object against every other border object in this way. When you've finished this, the border list contains one object for every line in your polygon map... and it also tells you which polygons are neighbours of the line... and even where the line is.

Once you get to this point, you then want to go further and create the second list I mentioned... but more on that later if needs be. Try implementing this first idea and let us all know how you go!

Cheers,

Timkin

[edited by - Timkin on May 9, 2002 9:52:58 PM]

Thanks again Timkin,

I've implemented what you've suggested so far. If you really want to see what I've done, I've uploaded them to:

This place
(it seems my ISP's webspace doesn't like me, so it's on Yahoo)

(Not all of it is optimised, especially the checking for the same edges, and not much of it is commented)

If you do look at the classes, could you in particular look at the nested loops inside the method createMap() in the file 'ConnectivityMap.java'. It's a bit messy, and I'm not entirely sure it'll work. Obviously, it's all in Java, but if you understand C you should get along fine.

If there's anything wrong with what I've done, please point it out, and I'll have a go at fixing it. Otherwise, please tell me the next step!!

Thanks again
Stewart Holmes

[edited by - ServantOfGlaaki on May 13, 2002 3:36:20 PM]

I know you''re not going to like the sound of this... but I have a very important seminar to deliver on Monday and so I wont get a chance to look at what you''ve done until after that... sorry for the delay... but I''ll get back to you when I''ve got a spare moment.

Cheers,

Timkin

Not to sound impatient, but have you had a chance yet Timkin?

Thanks
Stewart Holmes