Существует ли алгоритм для создания Smart Snake, чтобы заполнить всю карту, если это возможно, без столкновения с какой-либо частью его тела или стены - PullRequest
Новая
       37

Существует ли алгоритм для создания Smart Snake, чтобы заполнить всю карту, если это возможно, без столкновения с какой-либо частью его тела или стены

1 голос
/ 04 марта 2020

Пожалуйста, помогите мне, указав имя алгоритма или если у вас есть хороший исходный код для решения проблемы

Чтобы понять проблему,

Вот некоторые входные данные в JSON Формат соответствует их исходному изображению карты

{"wallX": [0,2], "wallY": [0,2 ], "startX": 0, "startY": 1, "maxX": 3, "maxY": 3}

enter image description here

{"wallX ": []," wallY ": []," startX ": 1," startY ": 4," maxX ": 6," maxY ": 6}

enter image description here

Правила

  1. 99 представляют стену. X & Y стены [index] обозначается wallX [index], а wallY [index].
  2. 01 представляет начальную точку Змеи. X & Y, равное 01, обозначается startX, а startY
  3. maxX представляют столбец двумерного массива, а maxY - строку двумерного массива. И maxX, и maxY <= 9 </em>
  4. На исходной двумерной матрице / карте любая плитка, отличная от 01 или 99, будет плиткой 00.
  5. Змея может только Переместиться в 00
  6. Переместить змею 4 способами [влево, вверх, вправо, вниз]

Ввод программы соответствует формату JSON.

Выходные данные программы должны быть:

  1. 2-мерный массив состоит из 99 и / или (от 01 до 0X) без остатка 00 плиток, которые Представьте, что карта решена
  2. Начальный 2-D массив, представляющий, что больше нет возможного движения влево, но есть по крайней мере 1 из 00

Вот некоторые другие входные данные, соответствующие с двумерным изображением их выходных данных

{"wallX": [0,0,1,2,3,4,5], "wallY": [0,4,5,1,1 , 1,4], "startX": 0, "startY": 3, "maxX": 6, "maxY": 8}

{"wallX": [0,1], "wallY": [0,1], "startX": 0, "startY": 1, "maxX": 2, "maxY": 2}

{"wallX": [0,2], "wallY": [0,2], "startX": 1, "startY": 1, "maxX": 3, "maxY": 3}

enter image description here

Я сделал свой собственный исходный код для решить эту проблему, но я хочу найти алгоритм, чтобы я мог больше узнать о том, как на самом деле бороться с этим / связанным алгоритмом / проблемой.

  1. Я пытался найти в Google, с ключевым словом например, «Fill», но большинство результатов показывает мне [Flood-Fill-Algorithm]. Большая часть Flood Fill, которую я прочитал, не может быть применена здесь, так как Змея или [LastNumber] должны быть смежными с [LastNumber + 1].

  2. Я также пытался найти про Pathing , но, похоже, PathFinding работает, если есть Start и Destination, но эта проблема, похоже, не имеет четкого Destination.

Пожалуйста, исправьте меня, если я не прав насчет этих ^

Заранее благодарю за помощь

...