# Pathfinding in non-grid-based 2D environment

This topic is 2765 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites

but I can't find algorithms for dynamically generating them

Because that is the hard part
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.

##### 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
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.

[/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 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 on other sites
Have you considered making the nav-meshes manually? I tried for a while to implement a good algorithm to do it automatically, but gave up when the effort seemed greater than just doing it by hand for the amount of meshes I needed to make. Not sure if that would work for your scenario.

http://mtnphil.wordpress.com/2009/05/21/nav-meshes/

##### 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.

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 16
• 30
• 9
• 16
• 22