Re: sokoban

["Paulo Santa Rita" <p_ssr@xxxxxxxxxxx>]

Oi Niski,
Tudo Legal ?

Tambem "infelizmente", estou muito ocupado e sem tempo pra pensar e me 
concentrar continuamente, como gosto e como a questao merece. Entretanto, 
ontem a noite, quando cheguei em casa, pensei um pouco no problema. Vou te 
contar agora o que vi.

1)As caixas e o motor andam em um assoalho quadriculado, que pode ter uma 
forma qualquer, ao sabor do inventor do jogo e dos diversos niveis.
Podemos escolher um plano cartesiano conveniente de forma que a cada casinha 
estara associado um par ordenado (Xi,Yi) formado por numeros inteiro e 
positivos. Isto implica, claramente, que o pavimento (assoalho) por onde 
trafegam o motor e as caixas e um conjunto de pares ordenados, todos com 
coordenadas inteiras e positivas.

Seja "A" (de "A"ssoalho) este conjunto. Assim, A={conjunto dos pares 
ordenados que caracterizam univocamente as casas acessiveis do jogo de 
sokoban }

Para que possamos distinguir as casas vazias das que estao ocupadas por 
caixas e pelo motor, facamos o seguinte :

Seja C0:A -> {-1,0,1,2,3,...} uma funcao tal que :

REGRAS :

C0(x,y) = -1 se a casa (x,y) estiver vazia
C0(x,y) = 0 se a casa (x,y) contiver o motor
C0(x,y) = N se a caixa N estiver na casa (x,y)

Apos o primeiro movimento a funcao C0 muda para a funcao C1, apos o segundo 
movimento a funcao C1 muda para a funcao C2 e assim sucessivamente, sempre 
obedecendo as regras estipuladas acima. Podemos, pois, dizer, que um jogo e 
uma sequencia de funcoes C0,C1,C2,C3,...

As funcoes Cn nos permitem descrever matematicamente um jogo. Todavia, nao e 
isto que queremos. Queremos encontrar o caminho Otimo que caracteriza-se 
pela quantidade minima de passos. Para ver como e possivel isso, sejam

(X0,Y0) e (X1,Y1) dois pontos no plano cartesiano. Qual a quantidade minima 
de passos inteiros que devemos dar para, partindo de (X0,Y0) chegar a 
(X1,Y1) ? Verifique que e o numero:

Min = modulo(X0 - X1) + modulo(Y0 - Y1)

O motor, em geral, vai de uma caixa para outra de forma a compor uma 
estrtegia vitoriosa, de forma que o numero acima vai ser importante em algum 
ponto de nossa investigacao. Devemos considerar tambem que pode haver 
obstaculos entre um ponto e outro. Neste caso, qual o numero minimo de 
passos ? Nao e dificil encontrar e e uma combinacao linear das duas parcelas 
acima. Mais tarde eu vejo isso.

DIAGRAMA DE UMA ESTRATEGIA

Uma estrategia pode ser descrita assim ( vou imaginar duas caixas e um motor 
)

1)O motor se associa a primeira caixa, da alguns passos com ela
2)O motor vai de um ponto vizinho a primeira caixa para um ponto vizinho a 
uma segunda caixa
3)O motor se associa a segunda caixa, da alguns passos com ela
4)O motor vai de um ponto vizinho da segunda caixa para um ponto vizinho a 
pr1meira caixa
5) volte ao passo 1)

O algoritmo prossegue ate que as caixas em duas caixas que chamaremos de 
destino e representaremos por D. Assim, D e o conjunto das coordenadas das 
casas de destino.

Resolver o problema significa transcrever o algoritmo descrito acima atraves 
da sequencia de funcoes Cn definidas tambem acima de forma que os passos 
dados sejam minimos.

Evidentemente que o problema ainda esta longe de ser resolvido, mas ja temos 
alguns instrumentos matematicos que podem descreve-los. Nao sei se sao os 
melhores, mas e um comeco. E entao, eu dei o passe : voce agora faz o gol ?

Um abraco
Paulo Santa Rita
4,1239,18072001











>From: fabio niski <fabio@niski.com>
>Reply-To: obm-l@mat.puc-rio.br
>To: obm-l@mat.puc-rio.br
>Subject: Re: sokoban
>Date: Tue, 17 Jul 2001 20:52:40 -0300
>
>Infelizmente não Paulo. E voce?!
>
>Paulo Santa Rita wrote:
> >
> > Ola Niski,
> > Bem-Vindo a Lista OBM !
> >
> > Voce estreiou propondo uma questao muito interessante ... Voce ja 
>conseguiu
> > algum progresso no processo de formalizacao do jogo ?
> >
> > Um abraco
> > Paulo Santa Rita
> > 3,1749,17072001
> >
> > >From: niski <fabio@niski.com>
> > >Reply-To: obm-l@mat.puc-rio.br
> > >To: obm-l@mat.puc-rio.br
> > >Subject: sokoban
> > >Date: Fri, 13 Jul 2001 21:09:47 -0300
> > >
> > >Amigos, está é a minha primeira mensagem no grupo!
> > >
> > >Bem, creio que muitos de vocês, amantes da logica, já ouviram falar
> > >sobre um famoso joguinho japones chamado sokoban.
> > >(p/ windows) http://www.sokomind.de/
> > >(p/ linux, vem no pacote games com o kde)
> > >
> > >Gostaria de saber, se alguem conseguiria matematizar o objetivo do jogo
> > >(levar as pedras ao lugares definidos, com o menor numero de passos
> > >possiveis), criando assim um algoritmo que mostre o caminho ideal a ser
> > >seguido!
> > >
> > >Essa foi a minha sugestão!
> > >
> > >Abraços..
> > >
> > >Niski
> >
> > 
>_________________________________________________________________________
> > Get Your Private, Free E-mail from MSN Hotmail at 
>http://www.hotmail.com.

_________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com.