I have a list of entities that looks like [{x,y,width,height}, {x,y,width,height}, ...]. This list is non-discreate, It doesn't follow a grid. entities can be positioned at floats like x:2.345

Most path finding solutions I've found like A* expect a discrete grid to perform the calculations.

I've looked at Theta* as a solution it supports non-discreate pathfinding on a navigation mesh.

Either way I need to convert this entity data into a Grid or Navigation Mesh. This is probably a common task but new for me. I'm doing this in Javascript and would appreciate any examples in that language.

also some entities will be moving in realtime and will effect future path generation of other entities.

enter image description here

  • \$\begingroup\$ Could you please provide a more concrete example of what your input data may look like? You may or may not need a navmesh depending on your possible input. Please give a visual example if possible. \$\endgroup\$ – wolfdawn Oct 28 '14 at 6:20
  • \$\begingroup\$ It sounds like by entities you mean rectangles? Could you please be more specific and provide an image, technically it's a graph, so A* would work fine. \$\endgroup\$ – wolfdawn Oct 28 '14 at 16:03
  • 1
    \$\begingroup\$ Does the black spots represent none passable areas? i.e you can walk anywhere on the white area, correct? Also is this a pretty realistic and common scenario and are the black spot in motion? \$\endgroup\$ – wolfdawn Oct 29 '14 at 14:12
  • 1
    \$\begingroup\$ I updated the answer and I welcome questions for clarification. \$\endgroup\$ – wolfdawn Oct 29 '14 at 14:25
  • 1
    \$\begingroup\$ @Zehelvion the black spots are 'hard spots' and the smaller black spots will be in motion. \$\endgroup\$ – kevzettler Oct 29 '14 at 17:20

new answer:

In the real world, since this field is not densely populated, simply tell the characters to move in the desired direction and once they approach an obstacle, to go clockwise or counter-clockwise around it (depending on which way is shorter).

enter image description here

To improve on this, you can walk the characters towards corners instead:

enter image description here

In the general case, you would send rays from the corners of the black rects like so:

enter image description here

The circles will be the vertices of the graph and the lines, the edges. Once the line hits the border of the stage, you need to recursively keep searching to the left and the right. I did not put it in the sketch but you also need to cast edges inwards. This however is the general case (which is hard could the field might be very densely populated).

Please note doing this pseudo-boolean operations on a 2d-mesh to get the desired navmesh or graph could be expansive so it's not something you want to do if your game worlds modifies itself in real time. It is more of a tool that could be used in advance. I strongly suggest going for the first approach if possible as it's much much faster.

old answer:

They don't expect a discrete grid, they expect a graph. You need to form a graph, perhaps by embedding your input in a navmesh.

Also, please consider caching paths by computing them "offline" (not during runtime) in advance to offload that process as it could get taxing, depending on the complexity of the graph.

  • \$\begingroup\$ What if this graph is changing in realtime because the entities are moving? How am I supposed to cache that offline? \$\endgroup\$ – kevzettler Oct 28 '14 at 15:55
  • 2
    \$\begingroup\$ You didn't say the graph was changing in realtime.. I don't think that is the common case so I didn't assume so. \$\endgroup\$ – wolfdawn Oct 28 '14 at 16:02

I would consider generating waypoint graphs instead. They're easy to work with, they give optimal paths, and are generally fast enough for reasonably small environments.

The optimal path will be a series of line segments, and each vertex in the path will either be the origin, the destination, or a vertex of one of your obstacles. So although your environment isn't discreet, you only really need to consider this discreet set of vertices.

So, you can build a waypoint graph with a node for the origin, a node for the destination, and a node for each vertex of each obstacle. Two nodes should have an edge between them iff the line segment between the nodes does not intersect any obstacles. The weight of the edge should be the length of this line segment.

If you have dynamic obstacles, a new graph will need to be regenerated repeatedly. If this turns out to be too slow, a number of optimizations are possible, but the best approach depends on how many static vs dynamic obstacles you have and how often the dynamic ones move.

Once you have this graph, you can run any pathfinding algorithm on it. A* is an option - it's usually used with grids, but all it requires is a graph and a distance heuristic. Since each node in your graph has spacial coordinates associated with it, you can use the usual distance heuristics (e.g., Euclidean distance if you allow movement in any direction).

Note that I've assumed your agents can fit though arbitrarily small spaces. If that isn't the case, we need to offset waypoints away from obstacles based on the agents' size, and use rectangles instead of line segments when checking if two nodes are connected.


I want to post my own answer that I eventually went for with this

Steering Behaviors: http://www.red3d.com/cwr/steer/

Essentially each frame you calculate a movement "force" on an entity. The force can take into account other entities positions. So in my case the moving entities would take a "Seek force" to move towards a destination and along their way they would apply an "avoid force" to any of the non-discrete entities and move around them.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.