Sign in to follow this  

Pathfinding solutions requiring backtracking: Looking for direction

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello, I'm new to these forums, someone suggested that I might find an answer to my question here. I apologize if this topic has already been discussed or answered elsewhere. I've been trying to develop an algorithm to solve levels for a game called Psychopath (http://www.k2xl.com/games/psychopath/index2.php) mostly out of interest. Its basically a 2D grid with movable blocks and immovable walls, the object being to reach the goal in a set number of moves. I've developed some brute force algorithms (with various heuristics) that work quite well for the lower levels. However, further levels require solutions that involve retracing over squares you've passed before (once blocks have been moved out of the way). These "backtracking solutions" are giving me a hard time, and I'm not sure how to approach this problem. Any attempt at an efficient solver so far has just been plain SLOW. I'm wondering if there is any material or theory that deals with problems of this type. I hear a lot about A* but nothing about variations that allow retracing step solutions. Any help would be appreciated. Neema

Share this post


Link to post
Share on other sites
A* guarantees the shortest possible path. It is the perfect solution

I don't know what you mean by moveable blocks. The levels I played just involved moving the unit to the goal in the shortest possible mode. Other than the unit I didn't notice anything else that could move.

-me

Share this post


Link to post
Share on other sites
The first 9 levels I think don't use any movable blocks. Thereafter, every level uses moveable blocks. The first level that requires backtracking steps is 27. (The game is actually quite fun when you start playing it) It might take a while to get to level 27 though, so let me just sketch an example here to bring concreteness to the problem.

LEGEND
B - Block (Blocks can only be moved into an empty space or on top of the goal)
W - Wall
P - Player position
G - Goal position
. - Empty space

Consider this simple scenario: This isn't a real level, its just to illustrate the backtracking problem (sorry the ascii art isn't the greatest)


WWWWW
W.B.W
WPBGW
W.B.W
WWWWW


The solution requires 8 steps, and backtracking.
In this case there are two symmetric solutions. Heres one:
UP, RIGHT, LEFT, DOWN, DOWN, RIGHT, UP, RIGHT

In this case it would be easy to find the solution by exhausting possibilities, but most levels that require backtracking are infinitely more complex than this scenario.

Share this post


Link to post
Share on other sites
You could probably handle moving blocks by branching on the space of maps, where the two resulting maps depend on not moving the block or moving it. In situations where the block is backed up against something else, you wont get a branch. When you branch maps, you'll need to split your seach problem into two, making sure to invalidate paths in one of the maps where the block moved over a previously open square.

Now, this sounds like a computationally intensive problem and it would be, except for the fact that you're given the feasible search horizon (in the form of the number of permissible moves). So, only search out to that horizon. I'd use A* and a Manhattan Distance as the heuristic, since this is guaranteed to never overestimate the number of moves needed to get from any square to the goal.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Quote:
Original post by Timkin
I'd use A* and a Manhattan Distance as the heuristic, since this is guaranteed to never overestimate the number of moves needed to get from any square to the goal.


I actually implemented this already and it works great for levels without blocks. Except for 1 level.. it finds a solution that is two moves longer than it should be, but I'm convinced its a silly bug. EDIT: Fixed

Quote:
Original post by Timkin
You could probably handle moving blocks by branching on the space of maps, where the two resulting maps depend on not moving the block or moving it. In situations where the block is backed up against something else, you wont get a branch. When you branch maps, you'll need to split your seach problem into two, making sure to invalidate paths in one of the maps where the block moved over a previously open square.


Timkin, this sounds like what I was thinking I had to do, but am troubled on exactly how to do it. When you said the problem was computationally complex, I think its an understatement. Wouldn't a branch have to occur on each block, in each possible direction is can be pushed? In the worst case, thats 4 branches per block. If thats the case, the number of branches grows awfully quickly. Especially with levels having many blocks that need to be pushed. Maybe its simpler than I'm thinking, but I'm having a hard time wrapping my head around this one.
EDIT: Sorry, of course the block can only be pushed in one direction (or not) from the current state, since your only on one side of the block at any given time.

As for backtracking, how would this be handled? For example, in the case of the small map I showed above. Suppose you move up and right. Then A* checks available moves and finds there are none, since the space on the left is in the closed list, and the remaining are illegal moves. It seems as though the closed list would need to be wiped clean everytime a block was pushed to account for this possibility.. but that would defeat A*. Anyway I'm not sure.. I'll keep mulling over it.

[Edited by - neemo_t on May 26, 2007 12:53:47 AM]

Share this post


Link to post
Share on other sites
Very sorry to double post.

Quote:
Original post by Timkin
you'll need to split your seach problem into two, making sure to invalidate paths in one of the maps where the block moved over a previously open square.

EDIT: I got this working, handles even backtracking cases. Unfortunately on complex levels heap memory runs out due to constant splitting of the search. I suppose the other option is something recursive, but I imagine this would just stack overflow.

[Edited by - neemo_t on May 28, 2007 12:39:29 AM]

Share this post


Link to post
Share on other sites
Good to hear you got it working. Now, to keep it working on complex maps...

Make sure that you double check whether pushing a block gives you a map you've aleady considered. This will often happen where you push a block, advance a few moves and consider pushing it back. If you can prune these duplicate cases you'll save some memory (assuming you haven't done this already of course).

As for the larger problem... make sure you don't search any map deeper than the cost supplied as the path length target. You could probably also constrain the search by keeping only a finite number of possible maps at any one time... or simply try some of the memory bounded variations of A*.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Quote:
Original post by Timkin
Make sure that you double check whether pushing a block gives you a map you've aleady considered. This will often happen where you push a block, advance a few moves and consider pushing it back. If you can prune these duplicate cases you'll save some memory (assuming you haven't done this already of course).
Timkin


That is a good idea. I hadn't actually considered that yet. My only concern is when the number of "pending states" (states that are produced by pushing blocks) is large, checking whether a new "pending state" is not already considered might get expensive. I guess some kind of hashing might do the trick though.

I also found a way to manage the memory problem as well, but tracking old states for comparison might become a memory problem again. I'll give it a try though.

Thanks for the suggestions Timkin. They have been helping a lot.

By the way, I've been doing this project in java since I never imagined it would get as far as it has. I know a c++ implementation would probably be infinitely faster, but I was wondering if you are familiar with any java JIT compilers? The reason I ask is because my code base has become large and the task of porting the project puts me off :P I'm hoping a JIT compiler might give a performance boost enough to handle some of the tougher levels, without having to redo everything in c++ :X

Share this post


Link to post
Share on other sites
As long as you're using an admissible heuristic, you don't need to wait for a path length to get too long before deciding it is not the solution. You know it is not the solution as soon as the current path length plus heuristic value is greater than the maximum length allowed.

For hashing states, look into zobrist hashing. It is a very efficient way to generate hash codes for this type of problem.

If memory is the biggest problem, try using iterative deepening A*. You already know the depth of the solution before starting, so really there wouldn't be anything iterative about it.

Share this post


Link to post
Share on other sites
Zobrist hashing huh? Never heard of it before now and I'm a little fuzzy about how it works.

From what I gathered, each possible state a POSITION can be in has a (ususally) 64-bit random number associated with it. So in other words, lets say BLOCK/WALL/EMPTY are each assigned a random 64 bit number. Then, to produce a hash code for a particular BOARD state (many positions), you XOR the numbers of all the other spaces with the current space? Is this right?

I also read up about transposition tables, and it seems like one would be required here. By hashing states I may inadvertantly invalidate a correct move into a state that has been previoused hashed (not a collision, just another transposition to the same state) by an incorrect path. In other words, there needs to be an efficient way to invalidate/remove entries in the hash/transposition table once a particular path has been abandoned. Is there an efficient method for doing this?

The only idea I can think of is that each potential state of the A* algorithm has its own "board state hash table" which is essentially just a copy from its parent.

Anyway just some thoughts. I feel like I'm losing to the problem at this point :p

Share this post


Link to post
Share on other sites
The state for a given problem can be described by the position of the player and the position of each of the movable blocks. The walls and empty spaces cannot change, so they are the same for every state of the problem.

To make a zobrist hash key using the player's position and the position of each block, you would xor together the values for the player at his current position and the values for blocks at each of their positions. For each position, you'd have two random values, one for when it is occupied by a player and one for when it is occupied by a block. When the player moves, you can generate the hash code for the new state by just a few xors (for the player's movement and possibly for a block's movement). To compare states for equality, check that the player's position and the positions occupied by movable blocks are the same. The odds of a hash collision are very low, so you won't need to do many equality checks, and when you do find that you've already visited a state you can immediately terminate that branch since you've already found a path at least as short as the current path that leads to that state (assuming the heuristic is admissible).

With iterative deepening A*, you wouldn't have to store lots of states at all. It's just a depth first search, down to the depth of the solution length. With an admissible heuristic, you stop descending whenever you encounter a state where the path length plus hueristic value is greater then the solution length. This can be easy to implement and has an extremely small memory footprint, while still finding optimal solutions and using a hueristic to reduce the size of the search space. In fact, the only advantage of A* over IDA* for this problem would be A*'s ability to recognize states for which it already has a shorter path.

Share this post


Link to post
Share on other sites
Thanks for the clarification on zobrist hashing 8) I'm going to try implementing it today.

I use the manhattan distance heuristic, which I believe is admissible in this case. I also think I use some form of iterative deepening A*. As you describe, I don't expand nodes where f > maxMoves. Unfortunately, this doesn't work quite as well as you'd think. Most levels have a very large maxMoves. Like around 150~200. One level even has 616 :X All large boards are 21x21 which means the largest manhattan distance you can get is 42. In other words, you need to move a whole bunch of times before f > maxMoves and you can start cutting down those branches. The worst part is that the algorithm has likely made a mistake in the first 1-10 moves, it takes forever for the branches to exhaust and find the correct path :X

I think hashing states will be a huge improvement though, I imagine many many redudant states are produced by pushing blocks back and forth. Or at least I hope :P

The only other thing I can think of is using a better heuristic. Do you know of any other admissible heuristics? I might try making one up. Something that basically increments the manhattan distance when it decides there are walls between you and the goal.

Share this post


Link to post
Share on other sites
One heuristic that comes to mind is the shortest distance from each space to the goal, ignoring movable blocks. The boards are fairly small so each of these distances can be computed in advance.

Some techniques developed for sokoban might also be useful, since sokoban has the same mechanics as this game, just a different goal.

The solution length of the puzzle with a number of the blocks removed is also an admissible heuristic, since removing blocks can only make the path shorter. Maybe solve the puzzle with some of the blocks removed at random. Or solve a puzzle where all the blocks greater than or less than a certain distance from the player are removed. I think that the path lengths for solving for the number of moves required to get a certain distance from your current position and then adding that to a solution where all the blocks that are within that distance are removed minus the chosen distance would even be admissible.

Share this post


Link to post
Share on other sites
Vorpy's comments have triggered another idea from me that might speed up your solver. Throw away your progressive search (i.e., search from the start node) and perform a regressive search (i.e., searching backwards from the goal state.

You can use a Distance Transform (regressive flood fill) for your search rather than A*, since you know that the heuristic cost for A* is going to be a gross underestimate on most boards and hence not useful in directing search. For the small boards the DT is very quick since the goal is known and fixed in time and thus the additional cost for solving boards that have an open path between the start and goal nodes (over A*) is minimal.

If your DT doesn't find an open path, then you need to consider permutations of the board generated by block movements, as you are doing now. For each permutation, recompute the DT starting at the lowest cost square adjacent to the pre-moved block (or adjacent to the post-moved block if this square is blocked now).

You can trim your search space by stopping your DT at any square that has a cost equal to the permissible plan length, as you are doing now.

You could just do a regressive A* search, or perhaps even a bi-directional and concentrate on regions of the state space that show the most promise for a short path.

Keep us posted as to how your solver goes please.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
To save memory, instead of storing entire maps, store the movement of a block and a pointer to the previous map (which is just the movement of a block, and a pointer to the previous map, etc).

Then write a function that makes that difference transparent to the end-user code. While this will increase time costs, it will reduce space-costs. And while you can always wait longer, you can't always allocate more memory. ;)

Share this post


Link to post
Share on other sites
Thanks everyone for the posts.

Heres a bit of an update:
1. Memory isn't a problem for now. I've been using something similar to what NotAYakk suggested for a while now, and it seems to be working. (One board with rearraranged references in each additional state)

2. I implemented the heuristic suggested by vorpy:

"One heuristic that comes to mind is the shortest distance from each space to the goal, ignoring movable blocks. The boards are fairly small so each of these distances can be computed in advance."

This was an excellent idea. The only drawback was a small constant delay added to the algorithm's execution speed, but on average the code is almost 600% more efficient. One level that used to take 10 minutes to solve was done in 60 seconds :O This was a real spirit booster :)

3. I tried to incorporate state hashing into my code, but there is big problem with using this in my implementation. I don't follow a depth first approach, and therefore have a very difficult time "undoing/removing" entries from the hash table if a path has proven to be incorrect. As a result, my naive implementation often blocks the path to the correct solution. I'm still working on this though, I have a couple ideas left

EDIT: I got this working... but the additional overhead causes slower execution on average and it didn't result in solving any of the levels that were previous unsolved.

4. Between levels 1-35, there are only a few the algorithm doesn't solve (just runs forever) If I could get all 35 that would be half way :P

For anyone whos interested, you can take a look at the levels that currently don't solve:

BLUE = start
PINK = movable block
GRAY = floor tile
WHITE = goal
BLACK = wall

Level26 Level27 Level34 Level35

This is the one that used to take 10 minutes:

Level25

---
I haven't gotten around to the more complex ideas suggested by Vorpy yet:

"The solution length of the puzzle with a number of the blocks removed is also an admissible heuristic, since removing blocks can only make the path shorter. Maybe solve the puzzle with some of the blocks removed at random. Or solve a puzzle where all the blocks greater than or less than a certain distance from the player are removed. I think that the path lengths for solving for the number of moves required to get a certain distance from your current position and then adding that to a solution where all the blocks that are within that distance are removed minus the chosen distance would even be admissible."

These heuristics sounds like they are worth trying as well, after that first simple one showed such a great improvement. I will try them eventually :)

Timkin, I have also thought about a regressive search, but I never really pursued the idea. I'm not familar with distance transform, i'll google around to see what I can find.

At this point it seems like I have a lot on my plate 8) Thanks again everyone.

There was one other vague idea I had, but I'm not sure if its worth pursuing. What about partioning each board into sections defined by the walls, not blocks. Then solved each section and turned the problem into navigating a graph (with possible cycles in the solution :X) with much much fewer nodes.

[Edited by - neemo_t on June 10, 2007 5:25:37 PM]

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this