Jump to content
  • Advertisement
Sign in to follow this  
paul23

Polygon map (searching for information)

This topic is 2911 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

Hi,

As summer holiday starts again it's time to pick up another topic of computer science for me to understand :). (Last year I took the time to really understand C++ and write an A* pathfinding algorithm).


Now continuing on that topic something else caught my interest: currently I simply use a normal array for the "map".. However I can foresee that in a future "game" the collidable objects are polygons instead of simple rectangle.

Now I'm a bit dumbfounded on this subject, and having a hard time to find any information regarding this subject. So does there exist any information about this way of building a "map"?

IE: how do you store it, what are the actual advantages/disadvantages, how do people normally use them. Simply all basic stuff about what I call polygon maps... (Or the actual term which I should use for searching :P)

Thanks in advance,
paul23

Share this post


Link to post
Share on other sites
Advertisement
I seem to recall there was another thread recently on polygon maps, so you might search for that term and see what you find. Also, a Google search for 'polygon map pathfinding' led me to this, which looks like it might be relevant.

In any case, as I understand it at least, a 'polygon map' is basically the 'inverse' of a navigation mesh (and vice versa). There seems to be more info available on the latter than the former, so you might try searching for 'navigation mesh' and see what you can find. (There's lots of info on pathfinding in navigation meshes out there, so you shouldn't have too much trouble finding good references.)

Share this post


Link to post
Share on other sites
From what I can gather from your post you are talking about 2d games, correct? I am figuring you are moving from a 2d tile based game system and now want to move to polygons? What type of game(s) are you interested in doing this for, top down or side scroller? And what level/depth of compexity are you wanting to deal with? Or are you just getting a feel for the waters that are ahead if you choose to make the transition?

Share this post


Link to post
Share on other sites
Well actually navigation meshes is what I "want" to create, had forgotten the term after 6 months. Basically this idea was raised when I worked with my A* pathfinding algorithm a bit.. and I noticed in most maps had multiple cells next to each other with exactly the same cost. 1 big polygon would really speed up pathfinding a lot in open areas..

The problem ATM is the actual conversion of these polygons of my game world to a nav mesh.. Also what I call "location awareness" is something I have difficulty to capture in code. Simply point -> mesh should be faster than O(n) shouldn't it? And with the methods I've found in the few articles I read it simply stored the neighboring polygons in a list.. Isn't this very error prone and slow? - if anything changes to the mesh you always have to update all neighbors again.



Anyways, I'm using this indeed for a "top down 2d perspective". Typically one can think of RTS games and such. Though I'm still in the phase where I'm just needing to see what it can do and, more importantly, cannot.

Share this post


Link to post
Share on other sites
Quote:
Simply point -> mesh should be faster than O(n) shouldn't it?
If you mean identifying the mesh polygon that contains a given point, then yes, a spatial partitioning schemes such as a grid or octree can be used to quickly find the containing polygon.
Quote:
And with the methods I've found in the few articles I read it simply stored the neighboring polygons in a list.. Isn't this very error prone and slow? - if anything changes to the mesh you always have to update all neighbors again.
Considerations for a dynamically changing environment will be very different than those for a static environment, regardless of how things are implemented.

Is it your intention to support dynamic changes to the navigation map? (I've seen mention of algorithms for dynamic updating of constrained Delaunay triangulations online, but I haven't investigated these myself.)

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!