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

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

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.

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

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]

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]

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

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

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.

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