Расчет / отображение минимальной стоимости перемещения робота (позиции) по 2D сетке (массиву) - PullRequest
Новая
       17

Расчет / отображение минимальной стоимости перемещения робота (позиции) по 2D сетке (массиву)

1 голос
/ 15 мая 2011

В настоящее время я работаю над вопросом о назначении, который вычисляет стоимость перемещения для робота (позиция x, y).

Нам даны размеры двумерной сетки (двумерный массив) с несколькими препятствиями (символ ##). Ниже приведен пример сетки. Нам также дали стартовую позицию робота. На текущей позиции «стоимость» составляет 00 (стационарная).

.................................................. ........................................##........ ........................................##........ ........................................##........ ..........######################################.. ........................................##........ ........................................##........ ........................................##........ ....################..........00........##........ ....################....................##........ ....################....................##........ ....################....................##........ ........................................##........ .................................................. ..................................................

В задании требуется вычислить стоимость каждой неизвестной сетки (..), чтобы она показывала стоимость, которую должен сделать робот, чтобы добраться до этой позиции.

Горизонтальные перемещения +2 к стоимости предыдущей сетки.
Диагональные перемещения +3 к стоимости предыдущей сетки.
Робот не может пересечь и препятствие и должен объехать его.
Каждое значение должно иметь минимальную стоимость (например: меньшая стоимость перемещения по диагонали, чем по горизонтали и вертикали).

Ниже приведен результат, который должен быть у нас (отображаются только две последние цифры стоимости с некоторыми опущенными значениями, чтобы он был более читабельным):

http://i.stack.imgur.com/JiDl1.png

Прямо сейчас у меня проблемы с визуализацией / решением проблемы. Нам сказали, что это «морально как алгоритм сортировки пузырьков», когда каждый раз, когда обнаруживается новая минимальная стоимость, все пересчитывается.

Извините, если это ужасно запутанно, любые предложения (код или псевдокод будут приветствоваться)

1 Ответ

0 голосов
/ 15 мая 2011

Имхо, самый простой способ визуализировать проблемы пути - это соединенная сеть узлов (график), где соседние узлы (квадраты, в которые робот может перейти из текущей позиции) связаны друг с другом с помощью взвешенных ребер (вес стоимость перемещения между узлами). 

N     @     N -2- N -2- N
|\         /|\   /|    /
2  3     3  2  3  2  3
|    \ /    |/   \|/
N -2- N -2- N -2- N     @

N = узел, числа и линии - ребра с весами, @ - препятствие

Алгоритм Джикстры уже был предложен, для более подробной информации см., Например, http://en.wikipedia.org/wiki/Shortest_path_problem. Двоичная минимальная куча работает как очередь с приоритетами (afaik, A * + двоичная минимальная куча часто используется в играх реального времени из-за скорости).

Редактировать: Я предложил A * раньше, но если подумать, он не будет работать для кратчайших путей из одного источника - проблема такая хорошая.

...