At most three? Does this mean that you have no spaces where you will have a square of eight floor tiles? If you think it’s more likely that most of your tiles have have two neighbors, instead of three or four, you can use this to greatly simplify your pathfinding.
This is exactly what happens when I try to use any applet with the IcedTea Plug-In (in Firefox, in Ubuntu, at least). I’ve never gotten it to work for me. I’ve switched to using the Oracle Java Plug-In. (Suggestions welcome at my post on the subject.)
718 paths tested?!?
Sorry, perhaps I didn’t explain it well enough. What I meant was that when expanding a search node, I’d only expand in the available walk directions (up, down, left, right), negating the direction from which I’ve just calculated the values for. From what I understood, when you examine the next node towards the goal, you’d normal expand in all directions - including diagonals - minus those nodes on your closed list. I was under the impression restricting it based on non-diagonal movements only would speed up the pathfinder testing a little?
Wow, I still can’t word this properly!
Whoops! That was a worthless statement! I just realized what you meant, heh…
Ah, you can do a hierarchical version, which could offer some major increases in you pathfinding speed. Basically, it requires you to sort of ignore the fact that you’re on a grid in places. If you have “Hallways” (Places where several tiles only have two neighbors) you can condense hallways into single nodes in your pathfinder. Then, apply your heuristic to the end of these hallways instead of going through each tile in them each time.
This is a sort of pre-processing step that you can do. Basically, your pathfinding map will be different from your displayed map, in that all hallways become a single node, where the path cost is equal to the number of squares that you have to traverse in that hallway. A hallway ends at a room (A collection of more than one tile with three-or-more neighbors) or at intersections (A single tile with three or more neighbors). Then you’ll have your ‘rooms’, your ‘intersections’ and your ‘hallways’. These would become nodes and vertices:
Intersection: Costs ‘1’ to traverse. Holds a set of hallways that lead away. This is the point you find the Manhattan Distance from goal from.
Hallway: Costs the hallway’s length to traverse it. This is the primary vertex. No actual pathfinding should be done on it, unless your goal is inside of one (In theory, you can also have Deadend hallways, which are only important if the start/end of the path is in one).
Room: Keeps track of entrances (Hallways and Intersections that open onto it), and the distances between entrances.
Pathfinder would function differently based on where you’re starting and where you’re ending. (I’m using RIH to the abbreviate Rooms/Intersection/Hallway map)
- Starting in a room
1.1) Ending in the same room: Pathfind through the room to the end points. Then pathfind from start to each exit (Use the Manhattan distance, actually) and from end point to each exit. If the combination of any two is less than the distance across the room, pathfind from those exits across the RIH and see if any result in a better goal. (SECOND WORST CASE)
1.2) Ending in another room: Pathfind to the exits, pathfind across the RIH, then pathfind from the new room’s exits to the goal. (WORST CASE)
1.3) Ending in an intersection: Pathfind to the exits, then across the RIH to the right intersection.
1.4) Ending in a hallway: Pathfind to the exits, then pathfind across the RIH to the hallway’s two entrances, then to the place in the hallway (This computation is not costly, since it’s just iterating through the hallway). - Starting in an intersection
2.1) Ending in a room: Pathfind across the RIH to the room, then across the room.
2.2) Ending in an intersection: Pathfind across the RIH to the other intersection.
2.3) Ending in a hallway: Pathfind to the two entrances of the hallway, then check which is the best entrance. - Starting in a hallway.
3.1) Ending in a room: Pathfind across the RIH from the exits of the hallway to the entrances to the room, then across the room.
3.2) Ending in an intersection: Pathfind across RIH from the Hallway’s exits to the intersection.
3.3) Ending in the same hallway: Pathfind through the hallway, then check if there’s a better path from end of hallway to end through the RIH.
3.4) Ending in a different hallway: Pathfind from the exits to the entrances.
That’s probably ‘Nodes visited’. A* provides the best efficiency under optimal conditions. If it’s not an optimal condition (There is no straight line to the goal), then it’ll still be moreefficient than other options.
Because of the backtracking/straight line deviation that you created, it’ll exercise a lot more nodes at the start. If you were to have a more direct path, it’d find it much more efficiently.
That’s brilliantly explained, thank you. I like the idea of compressing a unified space (like a hallway) into a single point of traversal. As you point out, the cost is simply the ‘length’ of the hallway.
I could (theoretically) improve upon this a little by implementing the ‘forbidden’ routes, perhaps as a precalculated step - using the methodology that any concave space is technically impassable (such as a deadend hallway) - and treated as a zone. If the target end point doesn’t include this zone, it is effectively dropped from the search graph, since it doesn’t contribute in any way to any paths. That way, you’d save NN additional node checks (where NN is the area in tiles of the zone in question).
Would this be a useful addition? Or am I barking up the wrong tree?
It certainly can be useful. Really, what I just did was explain one style of the Hierarchical system that was mentioned earlier.
If you’d like, I can go a bit deeper into some Graph Theory stuff that will allow you to figure out other, deeper Hierarchies.
However, I do have some questions/cautions to think about that really end up depending on how you’re implementing your world.
- How often are you generating new maps? If you expect that your player will be able to cause new maps to be generated quickly/often, then a lot of preprocessing (Which is what the Hierarchical stuff is) will result in a lot of loading time between maps. Then if you end up throwing maps often as well, such as if the whole dungeon is lost if you return to town, then you’ll be wasting a lot of those loading times. (From what I read, you’re going to be hand writing the maps? That means that you can manually define the RIH map and the like, rather than leaving that to an algorithm).
- Are you implementing a ‘Visited Tile/Seen Tile’ system? Like, if you just step into your map, will your character have no knowledge of the map? If so, you’ll have to figure out how to merge this intelligent/efficient pathfinder, with an exploratory one. Otherwise, you’ll end up with the Omniscient Pathfinder Syndrome, or a Cowardly Pathfinder Syndrome. Which is to say, either it’ll seem to know where the best path will be upfront, or it’ll avoid crossing through unexplored regions when moving between known regions.
I’m glad you asked. I should imagine the following answer will either (a) further complexify or (b) simplify the solution.
The player starts off in a set location in the new map. They are shrounded by a ‘fog of war’, so to speak, with a view radius of about 3 tiles. Since there is code in place to uncover the ‘fog’ tiles when the player is within a certain proximity to them, I haven’t needed to implement any further complex view mechanics, since everything inside of the ‘fog’ area is ignored.
Please ignore my horrible graphics! Very early placeholders for now 
The player has just entered the map, and can only see within a certain radius.
The player has moved around, and the visited areas are clear to see.
There are intended to be two movement styles in the game - keyboard and mouse. Tapping W,S,A,D moves laterally, whereas clicking can move automatically to a specified tile. The pathfinding was never actually intended for enemy movement, since the enemies will not ‘move’, per se, but will only implement basic ‘back and forth’ motion to give the illusion of wandering (either walking back and forth on the X or Y axes).
The intention was to allow the player to click on a tile and have them move automatically to that space - thus needing some kind of pathfinding. It probably doesn’t look worth doing in the above screenshots, but it was more for the zoomed out view - like you might see in Desktop Dungeons. The fact that you can’t ‘click’ on a destination tile within the fog area means that scenarios involving pathfinding in ‘unknown space’ are never going to happen.
In answer to your other question re: the dynamic state of the map - the worst case scenario was to have maybe some locked doors, or impassable tiles that can only be traversed with certain equipped items (slime pit / protective boots etc.). They should be minimal interruptions, at best.
I hope this clears up my intentions!
That does help a bit.
Well, somewhat, but opens up another question. You mentioned, earlier, that you were thinking about how it’d work if it were ported over to a mobile device. To me, that means touch screen controls for the most part. And that seems lead me to think about mouse-only movement.
However, to your earlier question?
Static Dynamics like that don’t cause many issues. Because those spots just become another type of node in the RIH map, somewhat like an intersection. You just have a flag check to see if that intersection can be traversed.
Converting the two? Just need to add a visited flag to the RIH map nodes to see if you’re allowed to path through it.
Correct, that was my intial reason for adding mouse support to the game. Mouse clicks on tiles can be replaced by W,S,A,D movement on PCs, and mouse clicks on enemies to attack, pick up items or such can also be replaced by key presses (or the mouse!). Thus, touch screen capability is retained.
With regard to the static map; I refer to my earlier post regarding the possibility for only slight differences in the walkability of any particular calculated path. Would it be fair to assume that if the path is being traversed one node at a time (after the correct route has been calculated) that it would be fairly trivial to do a quick per-node check to see if the approaching tile is still walkable?
This goes back to my A- > B -> C example, but I think it’s still relevant in this instance.
I’m not necessarily backtracking on my decision to go A* on this project; but I think it’s worth considering all options in the event that I want to take a little from column A, and a little from column B.
It’s probably rather trivial to do a check on the path to see if it’s still open (Visibly open would be better). However, it depends on how long you’re planning your paths in front of you. If you’re going partial pathing. Like, in the RIH thing, only finding the real path across a room when you’re in it, then it’s probably not too bad to see if your current path is open. If you’re getting the full path and checking it each time, then there’s a good chance you’re going to be path thrashing. Especially of enemies respawn.
What I mean there is, say, you get the whole path from where you are to another room. And let’s say you pass through at least one other room to get there. If there’s an enemy in that room, moving around. Each iteration you:
- Check if the path is blocked.
- If blocked, find another path.
If an enemy keeps walking over your path and you path find every tick… You get the idea.
I’m sure I can improve my implementation, but UprightPath is correct: “Nodes visited” would be more clear. My implementation calls each potential end-point a path, so I’m checking each path to see if it ends at the goal. Sometimes you can see the algorithm appear to wiggle away from the destination, because the shortest path might still be in the opposite direction from the goal (as the crow flies). Ultimately, it will find the most efficient path (and at least as efficiently as other algorithms). I proved that in school once, but I’m just going to take everyone else’s word for it at this point.
This implementation is a simple, 8-directional, non-weighted A*. In my game, it does a good job even when navigating through lots of obstacles (like over a river and through the woods). However, I put a wall-clock timeout on the processing. If it can’t find a path in that time, I cancel the pathing, and the player has to walk a bit further “manually.” This is justifiable because the pathfinder shouldn’t be doing all the exploration (ok, that’s really just an excuse).
Next time I have a cup of coffee, I’m going to pour through this discussion for all the keen pathing lore.
Pathing an avatar toward a potentially far-away moving target (creature): The brute-force (and most precise) method is to re-path every step. Then you know you’re always on the optimal path to the target’s current position. This can be very CPU intensive (depending on the map).
Instead of repathing, I compute the path once, then walk along the path until you encounter (maybe with some radius of contact) the target. In the vast majority of cases (in my game), the enemy is charging at you, and the path is cut short. In cases where the enemy has moved away to another position (maybe it’s chasing someone else), the character ends up at the enemy’s initial position. At this point, I re-path to the new position, which is not usually very far away.
To improve this, a heuristic could be included: When the enemy’s current position is some distance from the current path’s endpoint (and not on the current path), cancel and repath. I haven’t actually implemented that step yet (because it’s a rare occurrence), but it sounds like a slight improvement.
Well, I was more talking about an interrupted path to a tile, not to a target.
Especially since he described enemies as oscillating instead of moving with a purpose. So, if you’re pathing across a large map, and computing the whole path and checking it for interruptions the whole way, an oscillating enemy will cross/interrupt the path multiple times. And there’s a high likely hood that the new path produced will shortly be moved in.
For moving towards a target, I’d run a check through the path to see if it’s within some percent of the current distance left… So, say…
You plot the path to an enemy. At each logic check, you compute the heuristic distance (Should cost O(1)) from each point in your path to the enemy. If the lowest distance is less than say half the distance left in your path, you don’t repath. If it’s more, you repath to the target.
This means that you’ll tend to repath only when you get closer to the target, and when you start having to repath, it’ll be a shorter path each time.
Of course, you could only start checking when the heuristic distance between yourself and the target is less than some threshold.
I agree, that’s a great way to go about it. I wasn’t offering a contradiction/alternate to your above concepts - I was just bringing up a different scenario, which is how things play out in my game. Lot’s of really interesting material here.
I think there’s a degree of complexity on assumption here that isn’t necessary for the project I’m working on.
I agree that the inherant problems with pathfinding in a node system where blockages and interruptions are present can be cumbersome and difficult to overcome, but I’m taking an approach that removes most of these problems completely. How?
By stopping the player.
Let’s say you want to go from point A to point G, and an appropriate path is calculated. Along the route, say, at tile D, you come across an enemy. In the above examples, people are generally suggesting methods of recaculating the path based on this (possibly new) obstruction and thereby increasing the load on the pathfinder.
However, my aim here is to simply halt the player and cancel out any further movement along that path. It’s then up to the player to either deal with the obstacle (fight it) or go somewhere else.
I appreciate this might seem like a dumbed down idea, and certainly one ignominious to the normal practices of pathfinding, but in reality - I’m not looking for a graceful solution where the player’s path can anticipate, overcome or circumvent dynamic obstacles. Simply bumping up against the obstacle en-route and stopping is more than sufficient for my needs.
In many ways, there are some benefits there. Clicking inside a room, only to have your player stroll over and bump up (and stop) against the door leading to that room, only serves to reinforce the fact that the player cannot simply ‘stroll where they want’ using this method. And, in fact, I would also say that as a player I would expect a pathfinding algorithm to at least attempt to take me as far as it possibly can (i.e. the door), leaving me to realise what I need to do to proceed to that area.
Too many times in C&C games I’ve ordered my units to a position on the map, and they’ve instead wandered off and wedged themselves next to a cliff - leaving me to wonder if that’s actually intentional, and whether there’s a blockade I need to deal with to proceed.
In my example above, the pathfinder assumes the player has a clear route to the room, but when the door is encountered, they are stopped. If the door is the only route in, then the pathfinder is actually technically finding the best route to the door, since that’s where they’ll be stopped, which is actually a desired artefact of this kind of dynamic perception of the local surroundings.
Hmm, that was perhaps a little more verbose than I’d intended. But in summary:
[i]
- The player does not need to circumvent dynamic obstacles (e.g. moving enemies), only be stopped by them
- The player will analyse surrounding obstacles during their path traversal
- It is not essential that the player (or in fact any moving enemy) is omniscient enough to predict obstacles before they become so, only that they are seen just before the moment of impact.
[/i]
I should imagine this simplifies the solution somewhat, as the pathfinding will always take place on the entire walkable surface of the map, and the (carefully selected) obstructions will be dealt with in real-time during the course of the path movement.
Floodfill:
For an RTS I usually use a floodfill pathfinding. (given that The grid is not too big, like 100x100 the performance is ok)
There are 2 advantages:
#1 An unlimited number of units can use this single path-map at the same time - given they want to reach the same destinationpoint.
(Moving a group, with members spread at random locations)
#2 The units can avoid dynamic obstacles without the need to recalculate the path
How its done:
You basically fill the map from the destinationpoint with “height” values. Just like filling an image with a color in a paintprogram.
This creates a topography.
The algorythm continues until no “untouched” passable field ist found.
Every new filled tile gets increased in “height” by one given the closes filled neighbors height +1.
Now when the unit walks to the destination (wich is at the bottom of the “hill”) It just needs to move to the neighboring field wich
has the lowest hightvalue.
The good thing: it does not matter where the units start from. There will always be a lower field to go to from anywhere on the map.
Avoidance:
When this field is blocked by a dynamic object, it just chooses another field.
In case there are bigger obstacles it could increase the height of the field its standing on by 1, thus filling possible dynamic traps.
(altering the topography)
You could even make the unit avoid dangerous regions, like an enemy base by increasing the fields-height there.
This makes these area last to be chosen if no other path is free.
(I have an implementation somehwere here in the sourcecode for CraftCraft 4k.)
Its slower than A* for a single path, but as stated it more efficient when dealing with many units, and dynamic obstacles.
The algorythm is also quite simple to code.
You could even increase the performance by precalculating a list of “standard” destination points , choose the one closes to the actual destnation and let A* take over on the
short distance.
This way you can have hundrets of units walk on a map with almost not CPU power needed.
(trading Memory for Performance )