Рубин и указатели

Question

Я программирую Dungeon Generator для небольшой игры.

Подземелья состоят из комнат.A room имеет connections в другие комнаты.

room.connections = [room_a, room_b]
и
room.number = 1 # unique id

Теперь мне нужно выбрать комнату по ее номеру.

Сначала я сделал это с помощью метода recursive_scan, который не сработал, потому что комнаты могут привести к кругу, что приводит к ошибке StackOverflowError.Поэтому я поместил массив с именем already_scanned с номерами комнат, которые уже были выбраны в аргументы метода.Тогда он не сканировал все комнаты - кстати, я понятия не имею, почему, по моей логической непонятности, это должно было сработать.

Затем я попытался собрать все комнаты также в массив, а затем выполнить итерацию массива дляразыскиваемая комната - но здесь у меня проблема, каждая комната в основном связана с любой другой комнатой, по крайней мере, с некоторыми другими комнатами между ними;таким образом, массив становится равным dungeon_size * array_of_rooms.length.

Теперь мне нужен явный указатель - я знаю, что почти каждая переменная в ruby ​​является указателем, кроме Fixnums и Float (и, возможно, некоторых других).Несмотря на то, что массив становится большим, поэтому мне нужен реальный указатель.

(я также пытался настроить массив object_ids и загрузить их через ObectSpace, но, к сожалению - потому что мне часто приходится загружать комнаты -комнаты с требуемым object_id уже переработаны, как объясняется в сообщении об ошибке.)

Это мой метод рекурсивного сканирования:

def room(number)
  recursive_scan(@map, number, []) # @map is the entrance room
end

private

def recursive_scan(room, number, scanned)
  scanned << room.room_number
  if room.room_number == number
    room
  else
    r = nil
    room.connections.each do |next_room|
      if !scanned.include?(next_room.room_number)
        r = recursive_scan(next_room, number, scanned)
      end
    end
    r
  end
end

Answer 1

Все в Ruby уже является ссылкой.

Почему бы просто не поддерживать индекс комнаты?

rooms[room.number] = room

Тогда вы можете получить что-нибудь с помощью rooms[i].Я бы постоянно обновлял индекс, просто изменяя метод initialize для Room.

def initialize
  rooms[self.number] = self
  . . .
end

Это не займет много места, поскольку массив - это просто индекс,на самом деле нет копий комнат.Каждая ссылка, полученная из массива, по сути та же самая вещь, что и ссылка, полученная с помощью любого другого механизма в вашей программе, и единственное реальное различие между ссылкой и классическим указателем - это небольшие издержки на сборку мусора.Если комнаты когда-либо удаляются (кроме как непосредственно перед выходом), вы захотите установить rooms[x] = nil при удалении.

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

Answer 2

Это классическая задача о графе.Использование библиотеки графов решит большинство из этих проблем.Попробуйте использовать rgl самоцвет.

Определите каждую комнату как вершину на графике.Соединения будут по краям.

require "rgl/adjacency"

map = RGL::AdjacencyGraph.new
rooms.each {|room| map.add_vertex room}
rooms.connections.each {|room1, room2| map.add_edge room1, room2}

Теперь вы можете проверить, соединены ли две комнаты напрямую в O (1):

map.has_edge? room1, room2

Или получить список всех комнат:

map.vertices

Вы также можете получить список всех смежных комнат:

map.adjacent_vertices(room)

Answer 3

Действительно хакерский способ получить все комнаты в памяти:

all_rooms = ObjectSpace.each_object(Room).to_a

Answer 4

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