Re: heap.e ?? SNAKER
=20
Sorry it took some time to reply. I'll be short, since the
'pathing' thread seems to be more relevant to your problem.
=20
Of course, I had forgotten how the snaker algorithm worked:
the tail follows the numbers (1-4) while cleaning them up.=20
=20
This is ok, but a bit difficult to deal with, since you may need
to stack all the 'state variables' that you want to use in the
search. This would include all the segments of the snake.
=20
> =3D>The snake is arbitrarily large. (and grows when he eats something)
> I don't particularly want to move the star. What would be=20
> preferable, is for the snake to be aware that its tail is=20
> moving also, and if it can't reach the star at a particular
> moment (ie it's tail is in the way) then it moves into a
> 'holding pattern' until it can reach the star safely.
I see. What I meant with suicide, is when the game could clearly
_never_ evolve to a state where the star can be eaten. If the star
could possibly be eaten sometime in the future, the search should
discover this, even if it meant searching hundreds of moves ahead.
=20
> =3D>Snake grows in length every time it eats something.
This is where we go from 3-d state search (length 4 snaker) to
an n-d state search (length 5+)...
=20
> That is what I don't know how to do. How to find a path from point A =
to
> point B. Further explanation of this would be appreciated (examples? =
one
> can always hope.)
> Just like the star can be blocked by the snake itself,
> the tail could be blocked also. However, by the time the snake=20
> gets there, the tail> would have moved to a new position. (it
> doesn't always happen, but it does happen)
The 'paths' I'm talking about are not 2-dimensional. I bet you can't
solve the snaker problem only by finding 2-d paths. For example:=20
sometimes snaker may need to coil up for some time inside a room,
while waiting for his own tail to 'pass by' so he can continue.=20
=20
To solve this, the path must go from one snaker game state to=20
another without killing snaker. You must search these states, not
only the 2d maze.=20
=20
> State spaces?
Yes, Mr. Trick. Hyper dimensional state spaces. :)
=20
Perhaps you should experiment a bit with ordinary 2d mazes first.
I know the snaker problem can be solved, but I'm not sure with
what heuristics, or how fast it would be. I have a vague outline
of the algorithm in my head:
=20
A snaker game state would be stored as a list of snaker segment
positions. These are the only variables in the problem, and=20
thus all that need to be put on the stack while searching.
The critical point is where you:
=20
1. Pop a snaker. I.e. all the segments in a given state.
2. Push all subsequent snaker positions (child states of the
current state) that the snaker would survive.
=20
Each such multidimensional snaker game state correspond to a
branching position in a simple 2-d maze search.
=20
A greater problem, and probably very cycle consuming, is to search
for a safe position. This would include searching backwards in a loop=20
through all the parent states for each child state examined, to find
an identical state.=20
=20
I could try to implement this if you like, but in the mean time;
don't hold your breath, ok?
=20
> Yes, a folded umbrella.
> I don't know why.
It looks very cool. That must be the reason!=20
=20
Yours Sincerely,
Barbarella
=20
|
Not Categorized, Please Help
|
|
