next »

[Glaiel-Gamer]

The red path is the path taken if I'm just checking 4 directions.
The green path is the path taken if I'm checking 8 directions.
The blue line shows a situation which can't be solved by either.

The grid does a fairly good job of not allowing overlap of circles (not doing any sort of distance check, just looking up position in the grid)

Anyway, is this solvable by tweaking the pathfinding algorithm itself, or do I need to rework the way I'm representing "walls"


(I'm trying to pathfind around the circles, the grid is just my representation of them.)

[TheSpaceMan]

Are you using a A* implementation? seems like that could work for this one. That or a complete list of what nod is closest to what node.

Or you could do some kind of procedural AI that tries to find the closest path, can step back on it self and create the path data internaly, and removes a part of the path if he return to the same point where he is.

Since I don't know enoguht about your current implementation other then the fact that it seems to be grid based and dynamical, i don't have so many suggestions.

[Glaiel-Gamer]

I'd like it to be grid based (some form of A* or dijkstras) but the problem is that blue line. As you can see, there's a big space it can move through there, but cause of the grid it would be treated as a wall and try to go around. I just need a way around that really without making the grid too small cause flash isn't exactly the fastest thing out there and it needs to be real-time and dynamic.

[BorisTheBrave]

You need to be more specific on your level data. Can circles overlap, do they always have a given space between them? Is there a minimum required width the player can squeeze through.

Because the example you've shown isn't great. If everything is circular, with no overlaps, then I don't need fancy algorithms, I can just walk in a bee-line, and skirt around any obstacles I come across.

It is is more complicated, but you can guarantee channels are always of a given reasonable thickness, then you can just use a fine enough grid.

In the worst case, you may have to give up on using a grid exclusively. For lots of circular obstacles, a Voronoi graph may be better.

[Eclipse]

Easy way: simply if the circle doesn't cover at least half a square don't make it a wall, to make that check if the middle of the square is inside a circle or not

then check also for collisions with the circle themselves to be sure to have a precise collision too.

Harder way: instead of a grid based method, use a graph structure! it's also way faster.. you can build it taking points around and then connecting the visible ones using raycasting with those circles

[jeb]

Can entities move in any direction, or only along the grid?

I'd do like Eclipse suggests, a graph representation. It sounds like some really fun coding, actually

[Pishtaco]

What Boris said: if the circles are always so far apart that you can travel between them, then you don't need a fancy pathfinding algorithm. For movement that curves naturally around circles, rather than coming to one, touching it, and changing direction, how about setting it up as a physics problem? Have a force taking your character towards the goal, and repellent forces from the centre of each circle.

[Michelle Disraeli]

From what I can tell, your problem is specifically coming from your use of a tiled grid, when the objects placed into your world are not constrained to the same grid.

There are two solutions that I can see:

Firstly, the less interesting one - simply use a finer grid size. However, as you point out, this could impact performance.

Secondly, don't use a regular grid. This requires some pre-processing time, but generate a series of nodes that are between the circles and that have enough clearance around them to allow passage. Once the initial system has been generated, it should then be possible to dynamically update this if required. The end of this gamasutra article discusses some options, and it should be relatively trivial to search for more information

On a related note, also see this other gamasutra article, which I consider essential reading for pathfinding algorithm design. Being able to minimise the route and make it more realistic is rather awesome

[shrimp]

Here are another couple of great navigation/pathfinding links:

Craig Reynold's steering behaviour stuff:
http://www.red3d.com/cwr/steer/Obstacle.html
There are lots of nice example applets and also an old GDC paper: http://www.red3d.com/cwr/papers/1999/gdc99steer.html (This approach is perfect if you can always fit between the circles, but can also be used in conjunction with a traditional path (example)

Amit's A* Pages:
http://theory.stanford.edu/~amitp/GameProgramming/
This is probably the best introduction to A*, including some nice analysis of what can go wrong. I do realise the A* isn't the problem in your case, it's just a great resource.

When you say "dynamic", can the obstacles move? If so, how much and how frequently? If the environment is really dynamic (like crossing a road, say) then you should consider not calculating a path at all and using a purely reactive system.

Also, a graph may not be a good idea if all (or most) of those circles can move, as the topology of the graph should change rather than just flagging edges as blocked/clear.

Thinking about pathfinding and moving obstacles, another advantage of using a finer grid (and maybe working on optimising or distributing the load of the A* if that's possible) is that it's pretty easy to update which squares are blocked.

I'm being a bit anti-graph here, but it just depends on what you expect to be happening in the game environment.

[Also I might be getting too hung-up on the word "dynamic" here, but it would have a big impact on what approach to use]

[Glaiel-Gamer]

dynamic means the player can move around circles

I was pointed to this article by someone
http://www.cs.colorado.edu/~ralex/papers/PDF/OOPSLA06antiobjects.pdf

And I think I'm going to play with that a little after I understand exactly what's happening there

[JohnH]

The problem with using a regular grid to block the locations of irregular shapes is that, unless your shapes and placement specifically take the grid into account, there will always be cases where the two don't match up well.  Your particular case actually illustrates this fairly well.

Using a finer grid could help.  In your example, it's not so important that the grid lines closely hug the edges of circles as the places where circles are too close together.  The place marked with the blue line is a particularly egregious example.  If two times the maximum width of a grid space (its diagonal) is greater than the minimum distance between two circles, then there will be cases where circles will block movement between them unintuitively.

I have a strong hunch that Michelle Disraeli's irregular grid suggestion is a very good one, although one must be careful that one isn't relying on other assumptions of regular grid use.  Using circular grid spaces arranged in a mesh-like arrangement might do the trick, although don't ask me as to how to create one of those.

Possibly the easiest solution here is simply to tweak the circle placement algorithm so that their borders are always well-centered on the grid.

[Glaiel-Gamer]

Ya I'm just going to alleviate this headache and just snap the circles to the grid so I can use a 2x2 square for every one