Simple Non-Grid Pathfinding for Dungeon Game
September 16, 2009 05:51 AM
I have perfected the AI of the game as much as I can right now, but the pathfinding is still an issue.
The monsters will only engage if you are in range of their aggro range, and they will not see you through obstacles. However, the monster stops following if you run around a corner and he can't see you anymore. This is what I need pathfinding for.
I need a simple pathfinding algorithm, or algorithm methods, to make the monsters dodge corners and run around obstacles, in a non-grid 2D world.
I am programming using ActionScript 3 and Flash, and please don't suggest A* unless you also have an idea on how to make the A* algorithm smooth and how I would use it in a non-grid/non-tile based game.
2,389
September 16, 2009 06:40 AM
Quote: Original post by CiubhranHere's one thing you could try regarding following the player around corners: when the monster loses sight of the player, have the monster proceed to the last spot where the player was sighted. If the monster reaches this point and the player becomes visible again, the monster can resume the chase at that point. (This would also probably be fairly reflective of how an intelligent agent would actually chase a target in an occluded environment.)
I have perfected the AI of the game as much as I can right now, but the pathfinding is still an issue.
The monsters will only engage if you are in range of their aggro range, and they will not see you through obstacles. However, the monster stops following if you run around a corner and he can't see you anymore. This is what I need pathfinding for.
I need a simple pathfinding algorithm, or algorithm methods, to make the monsters dodge corners and run around obstacles, in a non-grid 2D world.
I am programming using ActionScript 3 and Flash, and please don't suggest A* unless you also have an idea on how to make the A* algorithm smooth and how I would use it in a non-grid/non-tile based game.
'Real' pathfinding could certainly still be useful though (it could be used for investigating suspicious sounds, trying to 'cut off' the player by taking a less obvious path, etc.).
The two non-grid-based pathfinding methods I'm most familiar with are waypoint-based systems and navigation meshes. The latter has been discussed quite a bit here recently, so if you were to search the forum archives for terms such as 'navigation mesh pathfinding', 'path smoothing', 'string pulling', and the like, you'd probably find quite a bit of material. (Actually, since many of the discussions were fairly recent, you could probably just look through the last few pages of threads.)
Regarding navigation mesh-based pathfinding, here's a quick summary. Navigation mesh-based pathfinding can be difficult (or at least time-consuming) to implement, but the results can be very good. And yes, you can use A* (or a similar algorithm) with navigation meshes, and then apply path smoothing to improve the path to varying degrees (anywhere from a little smoother to perfectly smooth, depending on what algorithm you use).
If you don't need this level of sophistication though, some simple ad hoc behaviors might suffice. The 'go to last location that the player was spotted' behavior would be one example. As another example, for investigating sounds, you could raycast from the monster to the sound source, find the first wall that the ray intersects (if any), and then have the monster head for the endpoint of that wall closest to the sound source.
13,718
September 16, 2009 06:44 AM
Quote:
I need a simple pathfinding algorithm, or algorithm methods, to make the monsters dodge corners and run around obstacles, in a non-grid 2D world.
I am programming using ActionScript 3 and Flash, and please don't suggest A* unless you also have an idea on how to make the A* algorithm smooth and how I would use it in a non-grid/non-tile based game.
Well,sorry, but use A* :P
Whatever you do, you need an abstract representation of your world so that an algorithm is able to navigate around obstancles. Most abstractions are either a waypoint graph or a navigation mesh. Grids and tiles are just a special version of a waypoint/navigation mesh system.
Once you have choosen a representation you can use A* to calculate a path to your target. At last you need to smooth the movement of your agent along a path. There're several ways to smooth movement of a character along a path, which depends on your agent control system(i.e. physics based control system).
--
Ashaman
Edit: too slow ^^
982
September 16, 2009 08:45 AM
I'm going to drop a bunch of terms here with the idea that Wikipedia can fill you in on more detail and references. :-)
--- Graph search methods ----
Inherently, A* does not require a "grid." It is a graph search algorithm. A grid is just a special case. And there are a number of graphs which correspond to continuous worlds which can be searched to compute various kinds of paths.
You can find shortest paths in a continuous polygonal world by (1) forming the visibility graph for the vertices of the polygons and then (2) doing A* on this graph. These paths are guaranteed to be the shortest ones you can have in your continuous space! So this might be what I'd do.
If you do not need shortest paths per-se, then cell decomposition (e.g. "navmesh") methods are attractive. Basically, you break your world into cells, and then search over the graph (called the dual graph) whose vertices are the cells and in which an edge exists between two vertices iff the corresponding cells share a face; then you do A* on this graph. They tend to give "nice" paths which are relatively short but which are also not quite as "extreme" as those produced by the visibility graph method, which always gets as close to corners as possible. This said, you can get the "corner-hugging" behavior back if you like by running the string-pulling algorithm as a post-processing step on your path, or the funnel algorithm as a post-processing step on the polygon which is the union of the cells which make up your path.
There are also Voronoi methods, which are are pretty cool too but a little more complicated. What I like about them is that they distill the environment down to a very simple representation of its topology -- and give you what I would bet are the smallest graphs to search of any of these methods.
My personal suggestion would be to do distance-based A* on either the visibility graph or a navmesh.
--- Behavioral methods ----
You don't strictly need a graph search algorithm like A* to find a path in a continuous (or any) space. There are other methods (e.g. bug algorithms). But I would not recommend them for video games since really their appeal is that they are entirely sensor-based (for robotic applications), whereas in a video game you have perfect knowledge of your world, which you might as well use.
[Edited by - Emergent on September 16, 2009 9:45:56 AM]
--- Graph search methods ----
Inherently, A* does not require a "grid." It is a graph search algorithm. A grid is just a special case. And there are a number of graphs which correspond to continuous worlds which can be searched to compute various kinds of paths.
You can find shortest paths in a continuous polygonal world by (1) forming the visibility graph for the vertices of the polygons and then (2) doing A* on this graph. These paths are guaranteed to be the shortest ones you can have in your continuous space! So this might be what I'd do.
If you do not need shortest paths per-se, then cell decomposition (e.g. "navmesh") methods are attractive. Basically, you break your world into cells, and then search over the graph (called the dual graph) whose vertices are the cells and in which an edge exists between two vertices iff the corresponding cells share a face; then you do A* on this graph. They tend to give "nice" paths which are relatively short but which are also not quite as "extreme" as those produced by the visibility graph method, which always gets as close to corners as possible. This said, you can get the "corner-hugging" behavior back if you like by running the string-pulling algorithm as a post-processing step on your path, or the funnel algorithm as a post-processing step on the polygon which is the union of the cells which make up your path.
There are also Voronoi methods, which are are pretty cool too but a little more complicated. What I like about them is that they distill the environment down to a very simple representation of its topology -- and give you what I would bet are the smallest graphs to search of any of these methods.
My personal suggestion would be to do distance-based A* on either the visibility graph or a navmesh.
--- Behavioral methods ----
You don't strictly need a graph search algorithm like A* to find a path in a continuous (or any) space. There are other methods (e.g. bug algorithms). But I would not recommend them for video games since really their appeal is that they are entirely sensor-based (for robotic applications), whereas in a video game you have perfect knowledge of your world, which you might as well use.
[Edited by - Emergent on September 16, 2009 9:45:56 AM]
2,389
September 16, 2009 09:06 AM
Quote: If you do not need shortest paths per-se, then cell decomposition (e.g. "navmesh") methods are attractive. Basically, you break your world into cells, and then search over the graph whose vertices are the cells and in which an edge exists between two vertices iff the corresponding cells share a face; then you do A* on this graph). They tend to give "nice" paths which are relatively short but which are also not quite as "extreme" as those produced by the visibility graph method, which always gets as close to corners as possible.Just for completeness, I'll mention that you can get exact geodesic paths with navmeshes as well by building a 'rough' path using a graph search algorithm, and then using the funnel algorithm to compute a geodisic path through the 'channel' formed by the navmesh polygons.
(I'm not suggesting this is any better or simpler a solution than using a visibility graph, but it is an alternative.)
194
September 16, 2009 09:11 AM
Quote: Original post by jyk
Try regarding following the player around corners: when the monster loses sight of the player, have the monster proceed to the last spot where the player was sighted. If the monster reaches this point and the player becomes visible again, the monster can resume the chase at that point.
I have used this exact method and actually now prefer it to A* path finding simply because it gives your AI the appearance of far greater intelligence than it actually has. The algorithm is pretty simple and a FSM version looks like this:
if (state == patrol){ if (canSeePlayer()) { vTargetPosition = getPlayerPosition(); state = chase; } else if (return path exists) { follow return path } else { ... update normal AI ... }}else{ if (canSeePlayer()) vTargetPosition = getPlayerPosition(); walkAtTarget(); dropReturnPoint(); if (distance to target < radius) { waitTime += ndt; if (waitTime > 5 seconds) state = chase; } else waitTime = 0;}The idea is simple. If your patrolling you just check if you can see the player. When you can you start chasing the last position you saw him. If you simply always aim at the last position, and update it anytime you can see the player it just works. Watch the AI is it chases you through some pillars and its awesome - it'll follow you till it can see you through another path then run directly at you making it really look like your being chased. A* doesn't have the same realistic chase method - it might choose a really random path which is technically shorter but might not give the feeling of being chased.
The only important bit to remember is to drop a path on your way so your AI can return to its original spot when its done chasing the player. Otherwise your AI will chase through a few rooms and then get stuck.
A* works a charm for many many applications - but for chase AI, I really do prefer AI that actually chases you!
982
September 16, 2009 09:16 AM
Quote: Original post by jykQuote: If you do not need shortest paths per-se, then cell decomposition (e.g. "navmesh") methods are attractive. Basically, you break your world into cells, and then search over the graph whose vertices are the cells and in which an edge exists between two vertices iff the corresponding cells share a face; then you do A* on this graph). They tend to give "nice" paths which are relatively short but which are also not quite as "extreme" as those produced by the visibility graph method, which always gets as close to corners as possible.Just for completeness, I'll mention that you can get exact geodesic paths with navmeshes as well by building a 'rough' path using a graph search algorithm, and then using the funnel algorithm to compute a geodisic path through the 'channel' formed by the navmesh polygons.
(I'm not suggesting this is any better or simpler a solution than using a visibility graph, but it is an alternative.)
What's funny is that, while you were posting this, I was editing my post to add exactly this caveat. :-)
I am not clear, though, on whether the funnel algorithm gives a true shortest path in your environment (maybe it does)? I understand that it gives shortest paths in simple polygons. So if you break your problem into: (1) finding a "channel" in the navmesh, and then (2) finding a shortest path in this "channel," is this equivalent to finding a shortest path in the full environment? This I don't know, but I assume that if it's true there's a proof somewhere out there.
Since I know that visibility graphs do give shortest paths, I feel like that's the "safe answer" from an optimality point of view.
That said, there are other things that I really like about navmeshes. You can do things like this. And more importantly, the graphs tend to be smaller than visibility graphs.
982
September 16, 2009 09:23 AM
Quote: Original post by ptoQuote: Original post by jyk
Try regarding following the player around corners: when the monster loses sight of the player, have the monster proceed to the last spot where the player was sighted. If the monster reaches this point and the player becomes visible again, the monster can resume the chase at that point.
I have used this exact method and actually now prefer it to A* path finding simply because it gives your AI the appearance of far greater intelligence than it actually has. [...]
A* works a charm for many many applications - but for chase AI, I really do prefer AI that actually chases you!
It's not really an either-or, is it? The idea is,
1 - Estimate player's position to be last place the player was seen. (This reduces to the player's position when he can be seen).
2 - Find a path to this estimated location.
It would seem that any pathfinding algorithm -- including ones using A* -- would be fair game for #2, right? Though I do see that, if you are only ever moving to positions in LOS, then you don't actually need any pathfinding algorithms (unless there are obstacles you can see over).
Also, one could in principle make #1 smarter too, by trying to guess what the player will do (i.e., using a more sophisticated estimate). I vaguely remember reading an article about a guy who used a really simple particle filter to do this. Come to think of it though, you would only ever need to use "real" pathfinding for #1 if you made #2 more sophisticated as suggested here (or, as I said, if you have obstacles you can see over)...
2,389
September 16, 2009 09:36 AM
Quote: I am not clear, though, on whether the funnel algorithm gives a true shortest path in your environment (maybe it does)? I understand that it gives shortest paths in simple polygons. So if you break your problem into: (1) finding a "channel" in the navmesh, and then (2) finding a shortest path in this "channel," is this equivalent to finding a shortest path in the full environment? This I don't know, but I assume that if it's true there's a proof somewhere out there.Graph search + funnel algorithm doesn't necessarily give you the shortest path globally. For my purposes I've found that the paths returned are 'short enough', but by taking some extra steps, you can get the true globally shortest path. (It's fairly complicated though - probably more complicated than the visibility graph method.)
[Edit: As a side note, the reason I prefer the navmesh method is that with a little extra work, you can accommodate agents of different sizes in a flexible and uniform manner. I'm not sure if/how you can do this using visibility graphs (other than building a different graph for each size that you're interested in).]
982
September 16, 2009 10:27 AM
Quote: Original post by jyk
[Edit: As a side note, the reason I prefer the navmesh method is that with a little extra work, you can accommodate agents of different sizes in a flexible and uniform manner. I'm not sure if/how you can do this using visibility graphs (other than building a different graph for each size that you're interested in).]
Ah, yeah, that's nice... so you mark each edge with both a length and, say, a maximum agent diameter. That's really convenient. I'm not aware of any nice way to do something equivalent with visibility graphs. Though you could do this with Voronoi methods, which'd be kind of cool...
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
