A pesquisa de pontos de salto (A * com JPS) é aplicável a grades não diagonais?

Estou tentando acelerar o caminho e descobri o A * com o JPS . Ele basicamente remove os ladrilhos antes de adicioná-los ao conjunto OPEN.

Posso usar essa técnica com minha grade que permite apenas direções retas?

Se você ler o artigo , verá que eles listam isso como um problema em aberto na seção "Conclusões":

"Uma direção interessante para trabalhos posteriores é estender pontos de salto para outros tipos de grades, como hexágonos ou texes (Yap 2002). Propomos alcançar isso desenvolvendo uma série de regras de poda análogas às fornecidas para grades quadradas".

Portanto, para aplicar a Pesquisa de pontos de salto à sua grade ortogonal, você precisa decidir quais pontos devem ser considerados como pontos de salto nessa grade. Depois de pensar nisso por um momento, eu acho - mas não provou! - que as seguintes regras (baseadas nas Definições 1 e 2 do artigo, reformuladas de alguma forma para facilitar a leitura) podem funcionar:

Um nó y é o ponto de salto do nó x, na direção d, se y puder ser acessado a partir de x, movendo-se diretamente na direção d, e é o nó mais próximo de x para satisfazer pelo menos uma das seguintes condições:

1. nó y é o nó do objetivo,
2. d é um movimento horizontal e uma das células verticalmente adjacentes à célula y - d (ou seja, a célula um passo antes de y quando se move na direção d) é bloqueada, ou
3. d é um movimento vertical e existe um nó z que é um ponto de salto de y (pela condição 1 ou 2) em alguma direção horizontal d '.

Obviamente, as palavras "vertical" e "horizontal" podem ser trocadas na definição acima. O ponto é que precisamos escolher alguns maneira de quebrar a simetria para que apenas um dos caminhos possíveis para atravessar uma região retangular aberta seja considerado. Harabor e Grastien fazem isso preferindo caminhos "diagonal-primeiro", mas como não podemos fazer isso, temos que fazê-lo preferindo os caminhos vertical-primeiro (ou horizontal-primeiro).

Também pode ser possível desenvolver regras de poda alternativas que produzam caminhos mais "naturais", como preferir o rumo atual ao invés de virar ou talvez até preferir virar constantemente os caminhos da escada. A regra que dei acima é simplesmente a tradução mais direta da regra de Harabor & Grastien para uma grade ortogonal em que eu poderia pensar.

Na verdade, se você observar a definição de rota de 45 graus, sempre é possível transformar um caminho com rota de 45 graus em um caminho sem curva de 45 graus. E também é ótimo (você pode facilmente provar isso por contradição).

Portanto, a maneira mais simples é executar a pesquisa do ponto de salto e transformá-la em rota ortogonal.