Jump to content
  • Advertisement
Sign in to follow this  
Zeraan

Pathfinding in non-grid-based 2D environment

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

I've been doing a lot of research, but I think I'm looking in the wrong places. I'm working on a 4X TBS space game, and am now working on the space combat part.

In the space combat, all objects are squares, and don't rotate (although the sprite may rotate, their physical properties are always squares that are parallel to X/Y axis. The objects in combat can be of different sizes. There are no grid, other than the normal pixel X/Y positions.

I've looked at Navigation Meshes and Graphs, but I can't find algorithms for dynamically generating them, and I think there must be a simpler approach to this problem since all objects are squares.

There are two parts to this problem, creating a "navigable" map for the pathfinding algorithm, and the pathfinding algorithm. I'm very familiar with A*, having implemented it for the galaxy map, but I'm unsure if it's applicable in this situation. I guess it depends on how the "navigable" map is generated?

Share this post


Link to post
Share on other sites
Advertisement

but I can't find algorithms for dynamically generating them

Because that is the hard part smile.png
A very simple way is to
1. Lay a grid on your map.
2. Remove all cells which are blocked by static objects, environment ..
3. Merge 4 unbklocked cells, repeat this for larger blocks etc.
4. each remaining cell/block is a waypoint or a nav-poly.

More advanced algorithm and infos could be received over here.

Share this post


Link to post
Share on other sites

[quote name='Zeraan' timestamp='1332175975' post='4923344']
but I can't find algorithms for dynamically generating them

Because that is the hard part smile.png
A very simple way is to
1. Lay a grid on your map.
2. Remove all cells which are blocked by static objects, environment ..
3. Merge 4 unbklocked cells, repeat this for larger blocks etc.
4. each remaining cell/block is a waypoint or a nav-poly.

More advanced algorithm and infos could be received over here.
[/quote]

That sounds similar to a quadtree, except in reverse. Would generating a quadtree work, with each leaf a nav-poly, since all objects are squares and are parallel to axis? If so, then the only problem is how to use a nav-poly? I've seen some articles praising nav meshes as an better approach than waypoints, but not much on how to use them.

Share this post


Link to post
Share on other sites
Since your space combat mode is strictly 2D, there's no reason why the standard A* algorithm can't be applied. Just use a different grid for each different ship size.

Share this post


Link to post
Share on other sites
It looks like NavMesh is more trouble than it's worth. I guess I'll just force the ships to stick to a grid then.

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!