Кpатчайший пyть
- From
- Tretyakov Andrey (2:461/116.256)
- To
- Aleksey Skurihin
- Date
- 2002-08-30T18:42Z
- Area
- RU.ALGORITHMS
HIюшки, Aleksey!
26 Aug 02 Aleksey Skurihin писал All:
AS> Подскажите алгоpитм нахождеия кpатчайшего пyти.
AS> Исходник на паскале/делфи пpиветствyется.
AS> Необходим для маленькой стpатегии.
Лови
АЛГОРИТМ ПОИСКА ПУТИ В ЛАБИРИТЕ
Итак. У нас имеется поле размером 10x10 элементов.
Юниту требуется попасть из точки 1x1 в точку 6x6.
Заносим в конечную точку цифру "1"
0 1 2 3 4 5 6 7 8 9
0████████████████████
1██[] ██ ██
2██ ████ ████ ██
3██ ██ ██ ██
4██ ████ ██
5██ ████ ██
6██ ████ ██ 1 ██
7██████ ██ ██
8██ ██
9████████████████████
Далее. Цикл поиска всех единиц и установки вокруг них двоек (если конечно
есть куда)
0 1 2 3 4 5 6 7 8 9
0████████████████████
1██[] ██ ██
2██ ████ ████ ██
3██ ██ ██ ██
4██ ████ ██
5██ ████ 2 ██
6██ ████ ██ 1 2 ██
7██████ ██ 2 2 ██
8██ ██
9████████████████████
Тот-же самый цикл ищет двойки и расставляет вокруг них тройки
0 1 2 3 4 5 6 7 8 9
0████████████████████
1██[] ██ ██
2██ ████ ████ ██
3██ ██ ██ ██
4██ ████ 3 3 3██
5██ ████ 2 3██
6██ ████ ██ 1 2 3██
7██████ ██ 2 2 3██
8██ 3 3 3 3██
9████████████████████
Тоже самое но только теперь четверки
0 1 2 3 4 5 6 7 8 9
0████████████████████
1██[] ██ ██
2██ ████ ████ ██
3██ ██ 4 4██ 4██
4██ ████ 4 3 3 3██
5██ ████ 2 3██
6██ ████ ██ 1 2 3██
7██████ 4██ 2 2 3██
8██ 4 3 3 3 3██
9████████████████████
и т.д.
...
...
...
И вот, наконец-то мы добрались к исходной точке и записали туда "8".
0 1 2 3 4 5 6 7 8 9
0████████████████████
1██ 8 7 6 6 6██ 6 6██
2██ ████ 5 5████ 5██
3██ ██ 5 4 4██ 4██
4██ ████ 5 4 3 3 3██
5██ 7 6 5████ 2 3██
6██ ████ 5██ 1 2 3██
7██████ 5 4██ 2 2 3██
8██ 7 6 5 4 3 3 3 3██
9████████████████████
Теперь ищем вокруг цифры "8" любое меньшее число. Это "7". Запоминаем
его X,Y в какой-нибудь массив. Далее ищем вокруг найденной "7" следующее
наименьшее число и при нахождении опять запоминаем его X,Y в массив.
И так до тех пор пока не приползем к конечной точке 6x6.
В результате мы получили вот такой массив координат которые юнит извлекает
последовательно при движении:
┌─┬─┐
│X│Y│
├─┼─┤
│2│1│
│3│1│
│4│2│
│5│3│
│6│4│
│7│5│
│6│6│
Траектория движения будет такой:
0 1 2 3 4 5 6 7 8 9
0████████████████████
1██ 8 7 6 ██ ██
2██ ████ 5 ████ ██
3██ ██ 4 ██ ██
4██ ████ 3 ██
5██ ████ 2 ██
6██ ████ ██ 1 ██
7██████ ██ ██
8██ ██
9████████████████████
0 1 2 3 4 5 6 7 8 9
Вот вроде и все.
В случае если программа будет критична по скорости -
готов сварганить эту муть на ASMе.
И не забудьте предусмотреть глухаря, когда пути вообще нет.
---
* Origin: He жуй бутерброд => подавишься! Ж;) (2:461/116.256)