Задача 3: Дългото мазе

Сега сериозно. Тази задача е за напреднали, но държа всеки да се пробва на нея. Дадено ни е едно мазе, топка и финал. Мазето е случайно, то се прави само - можете да видите Creation кода на стаята. Целта на задачата е топката сама да намери най-краткия възможен път до финала. Понякога генератора прави такива мазета, че пътя е права линия, но често пътя ще е по забутан. Кликнете скрийншота да свалите .GM6 файла с основата. Тази задача дава 40 точки. Все пак е за изкуствен интелект (търсене на път).

И така, ето какво трябва да се направи:

Да се измисли алгоритъм за намирането на пътя. След това топчето да мине по пътя. Като се докосне в финала просто стаята да се рестартира и цялата процедура да се повтори. Може и евентуално пътя да се изрисува с черта, преди топката да мине по него.

Пояснения:

Оставил съм един обект pf. той е просто едно квадратче, помнещо число. Може да ви е полезен обекта за дебъгване ако ще правите търсенето със спомагателни обекти. Другия начин за търсене на път програмно е с масив или матрици.

Алгоритми:

Съществуват няколко алгоритъма за търсене на път, но двата най популярни са:

1. Метод на лявата ръка (или на дясната).
2. Метод на съседните върхове и теория на графите.

За тези алгоритми има много информация в гугъл, а и едития от двата дори не е подходящ за тази задача. Мисля че няма нужда повече да подсказвам, правенето с обекти на този алгоритъм може да нацака всичко, но правенето му с масив ще ви принуди да ползвате опашки и стекове... за което препоръчвам да ползвате Game Maker 7.0, защото в него няма бъгове покрай ds_* функциите.

Допълнителни неща:

Топчето да вземе всичките атоми - пак само, без намеса на потребителя, след което да иде до финала. Може да се реализира с търсене на най кратък път до най близки атоми. Не е трудно колкото звучи - тъпия алгоритъм е 3-4 евънта и 7-8 D&D действия! Е, и малко ползване на GML за правене на path ресурси.

Оценяване:

Колкото по читав и безотказен е алгоритъма, толкова повече точки. Колкото по кратки пътища намира - толкова повече точки. А ако е правилната имплементация на правилния алгоритъм, при това възможно с най малко код... сериозно може да черпя някой!

Успех!