Mapa, wspolrzedne, obliczanie sciezki Opcje

[Revan]

Jo!
Mam taka mape, ktora jest podzielona na kwadraty:

Kod

|--1--|--2--|--3--|--4--|--5--|
1     |     |     |     |     |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|
2     |     |     |     |     |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|
3     |     |     |     |     |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|
4     |     |     |     |     |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|
5     |     |     |     |     |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|

Teraz, zalozmy ze chce przejsc z kwadratu 2,2 (p) do 4,5 (k) z tym ze pola oznaczone x sa nie do przejscia. Tak jak tu:

Kod

|--1--|--2--|--3--|--4--|--5--|
1     |     |     |     |     |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|
2     |  p  |     |     |     |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|
3     |     |  x  |  x  |     |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|
4     |     |     |     |     |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|
5     |     |     |  k  |     |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|

Pomyslalem zeby zrobic petle. Kazda iteracja petli to jeden ruch. Przewiduje mozliwosc na skos. No i w kazdej sytuacji najprostrza droga bedzie wlasnie na ukos. No i zeby tak przejsc musimy przejsc przez pola 2,3 , 3,3 , 3,4 i 4,4. Na poczatek zastanawiam sie czy w ogole jest to mozliwe do obliczenia przez php. No, ale dajmy na to ze tak. Pierwsza iteracja - sprawdzamy czy mozemy wejsc na pole 2,3. Jezeli tak - idziemy do drugiej iteracji, jezeli nie - sprawdzamy czy sasiednie pola (zaczynajac od tych najblizej punktu docelowego) sa puste. Jezeli mozna wejsc na jakies pole, wchodzimy na nie, konczymy petle i wchodzimy do nowej, gdzie nastepuje ponowne liczenie sciezki, ale juz od nowego pukntu.
Dobrze mysle, i czy da to sie wykonac? Potrafil bym napisac takie cos, ale nie uwzgledniajac chodzenia na skos. Prosze o jakies sugestie, jak to rozwiazac.

[dr_bonzo]

O to mi chodzilo:
http://www.gamedev.net/reference/articles/article2003.asp

Summary of the A* Method

Okay, now that you have gone through the explanation, let's lay out the step-by-step method all in one place:
Add the starting square to the open list.
Repeat the following:
a) Look for the lowest F cost square on the open list. We refer to this as the current square.
Switch it to the closed list.
c) For each of the 8 squares adjacent to this current square …
If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.
If it isn't on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square.
If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.

d) Stop when you
Add the target square to the open list, in which case the path has been found, or
Fail to find the target square, and the open list is empty. In this case, there is no path.
Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path.

Ten post edytował dr_bonzo 26.05.2005, 22:50:26