Thanks Argus.

I already tried a similar style of A* for the color thing.
But I used it when the cube was near the tile it must pick up.
So maybe the problem was, that when A* only searches the 2..6 tiles around the colored tile, it could not find the solution because more moves where necessary for placing the right color on the right face. I''ll try that.

A thousand thanks to you all....




Grettings....

Regarding difficulty:

I have a kind of handicap implemented.

The player with the most points, needs the longest time to roll the cube.
The player at the end of the point list has the fastest cube.

Having taken a quick look at the game layout, I''d recommend using the Distance Transform Algorithm for pathfinding to the goal and a local brute force search to match the orientation of the cube to the required orientation, given the distance to the goal.

So, how does this idea work? The DTA efficiently determines, for each grid square, the minimum number of squares you must pass through to get to the goal and this is stored for that square. Now, if it didn''t matter which side touched that goal square, you''d simply follow the descending numbers to the goal. However, you also need to get the orientation right, so you could brute force search a tree of moves covering an expanding ring out from the cube. Take the simple case where there are 8 squares around the cube. Each of these squares has a number and hence an orientation the cube must be in if it is to start from that square and move to the goal (for a win). So, start enumerating possible moves that just involve the 8 surrounding squares and the current square that the cube is in until you find a state that matches one of the required starting states for the trip to the goal. If you cannot find such a state, expand the search to include the next ring of squares... keep going until you find the solution or find that none exists.

Since there will be other players, there will be dynamic obstructions in the game. You might like to include the ability for the computer to try to ''block'' the players path, causing them to recompute their move sequence. Any time the computers path to the goal is blocked (which will occur if it cannot find a next square with a lower number than it''s current square) then it will need to recompute its local search.

Does this make sense?

Cheers,

Timkin

Hmm I thought about moving near the tile and then searching, but considering that any kind of level might be implemented, some levels will require particular transformations to be done a long way away from the goal state.

Plus also I estimate an A* search will take only seconds to find an optimal path - efficiency is not a big issue.

Plus also I estimate an A* search will take only seconds to find an optimal path - efficiency is not a big issue.

If there other players and/or dynamic obstacles effectively blocking nodes in the search tree, then efficiency is very important. "Only seconds" is far too long.

I think we need to know more details about the gameplay before we can suggest anything solid.

fup - if you look at his problem, then you''ll see that he hasn''t got the bot working well *without* dynamic objects. It''s good practice to solve the easy problems before tackling the hard versions imho.

Once he can get the bot working effectively sans dynamic objects, the next step is to see if that produces a reasonable bot in the multiplayer game. If that fails, then and only then do we need to tackle the hard problem of pathing in a dynamic world.

Oh, is there a bot in the downloadable version? I didn''t see that. I just tinkered with it for a few minutes (great idea btw Martin) and then based my comments upon the screenshot and text on the site. (which describe much more complex environments and many opponents). I didn''t realize he wanted a solution to the simple problem.

Even keeping the game simple though I''d go for something like Timkin''s suggestion. Get to the 8 squares surrounding the target then just follow a pre-calculated sequence of moves.



ai-junkie.com

There''s no bot in the demo that I saw - but it''s quite apparent from his posts that the problem is not (yet) concerning the dynamic part of the game.

The problem with going close and then following a series of transformations is that the levels aren''t always going to be friendly ie. some of the later levels have a line of tiles connected at the end(s) with the tile in the middle. If you go near it you can''t perform the requisite transformations because you can only move forward and backward so you have to do them prior. So if we run toward the tile we''re going to end up running back out in many cases in the harder levels.

The branching factor is only 4 at maximum so I really don''t see how you can get faster while catering for all possible boards, unless the environment is dynamic, in which case one can still use the A* as a utility in a smarter bot. But the game might be more fun if the bots are really efficient with your only advantage being that you can alter the board state with your cube to buy more time (ie. block them off at key points).

Thanks for all guys!

I have tried the first idea of argus and it is very good.
A* is a bit slow when the bot must pick up a far tile.
So i let the bot search the nearest tile and look for a
path.
If the search takes to much time it rejects.
I also implemented a kind of ''round trip'', i don''t know how i should call it. Calculations are done only for one bot at one time. This is no problem, because when for example Bot1 is moving to the next tile, i can do the path search for Bot2.

The algorithm works very well, even on those un-friendly levels,
(when you only can move forward or backward).

Even with 8 Bots, there are almost no performance hits on my other computer (P2-233MHz).

The Fm1.1-beta has no bot, it also has no multiplayer mode.

My current version is almost full recoded.

I''ll give you some download links, when it is finished.

Thanks

Glad to see you got it going Martin - the game is actually surprisingly addictive even though I''m not a puzzle fan.