Поиск пути в 2D-массивах

Допустим, у меня есть эта карта 2D-массива.

{ 0,0,0,0,7,1,1,1,1,1,1,1,1 },
{ 0,7,7,7,7,1,1,1,24,1,1,1,1 },
{ 0,7,24,24,24,24,24,24,24,1,1,3,1 },
{ 0,7,23,23,23,23,23,23,24,1,1,3,1 },
{ 0,7,24,23,23,23,23,23,23,1,1,1,1 },
{ 0,7,24,23,23,23,23,23,23,1,1,1,1 },
{ 0,7,23,23,23,23,23,23,24,1,3,1,1 },
{ 0,7,24,24,24,24,24,24,24,1,3,1,1 },
{ 0,0,0,0,1,1,1,1,1,1,1,1,1 },

и у меня есть HashSet, полный целых чисел, которые определяют заблокированные плитки. Что было бы хорошим способом, чтобы, когда я нажимаю на одну часть карты, где стоит мой игрок, можно было найти путь? A* (с использованием узлов/и т. д.)? Что ты посоветуешь?

Спасибо.


java arrays path-finding a-star 2d
person test    schedule 21.07.2010    source источник
comment
Я бы порекомендовал для использования A * установить для заблокированных плиток значение int.MaxValue и забыть о любом хеш-наборе.   -  person nothrow    schedule 21.07.2010
comment
Где можно узнать об A*? Я попробовал Гугл. :\   -  person test    schedule 21.07.2010
comment
попробуйте википедию: en.wikipedia.org/wiki/A*_search_algorithm Кроме того, влияет ли стоимость перемещение по одной плитке отличается от другой?   -  person tsiki    schedule 21.07.2010
comment
@Dan _ что означают числа в вашем массиве?   -  person user85421    schedule 21.07.2010
comment
Они определяют изображения плитки в моей папке плиток, поэтому tile/t1.png будет плиткой [1] из плитки изображения []... и так далее.   -  person test    schedule 21.07.2010

Ответы (1)


arrow_upward
6
arrow_downward

Если размер вашего графика соответствует описанному вами примеру, вы можете безопасно использовать Алгоритм Дейкстры, учитывая, что он несколько проще в реализации, чем A*, и нет реальной необходимости в эвристических алгоритмах, если вы можете выполнить полный перебор почти за то же время :)

Что касается вашего комментария об «использовании узлов/и т. Д.», Это уже график, хотя и немного неуклюжий. Каждое значение массива является узлом, а «ребра» задаются смежностью в массиве. Заблокированные плитки можно сделать либо запретив смежность (т. е. просмотрев список заблокированных плиток, чтобы определить, доступен ли другой узел из текущего рассматриваемого узла), либо, как предложил Йоссариан выше, просто установите стоимость этой плитки на что-то, чтобы большим, чтобы быть практически бесконечным. Однако, если вы выберете последний подход, вам нужно убедиться, что эти плитки никогда не попадут в решение!

person Gian    schedule 21.07.2010
comment
Знаешь что? Это кажется немного продвинутым для меня. Я пойду изучать основы Java Game AI & Logic. У меня есть книги «Разработка игр на Java» Дэвида Брэкина и «Начало программирования игр на Java, второе издание» Джонатана С. Харбора и «Программирование убийственных игр на Java» Эндрю Дэвисона. Я вернусь к вам, когда прочитаю о них. Ура! - person test; 21.07.2010
comment
@Dan - это очень хороший ответ, и вам действительно следует его обдумать. Если вы боитесь графиков, просто используйте графическую библиотеку, например jgraph, в которой уже есть функция кратчайшего пути Djikstra. - person willcodejavaforfood; 21.07.2010
comment
Я посмотрю на jgraph. Хочешь связать меня с этим веб-сайтом? Не могу найти в гугле, потому что это просто общеупотребительное слово. - person test; 21.07.2010
comment
@ Дэн, если вы немного запутались в представлениях графов, возможно, матрицы смежности - хорошее место для начала чтения. Если вы переформулируете свой массив таким образом, проблема может внезапно стать намного проще. en.wikipedia.org/wiki/Adjacency_matrix - person Gian; 21.07.2010