CODEWITHSUNDEEP
rubypointers
Joern Akkermann
Joern Akkermann

Reputation: 3622

Ruby and pointers

I'm programming a Dungeon Generator for a litte game.

Dungeons are made of rooms. A room has connections to other rooms.

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

Now I need to pick a room by it's number.

I did this first with a recursive_scan method, which did not work because rooms can lead into circles, which throws a StackOverflowError. So I put an array called already_scanned with the room numbers, which were already picked into the args of the method. Then it didn't scan all rooms - btw, I have no idea why, by my logical undstandness it should have worked.

Then I tried to put all rooms also in an array and then iterate the array for the wanted room - but here I get the problem, every room is basically connected to every other room, at least with some other rooms betwenn it; so the array gets as big as dungeon_size * array_of_rooms.length.

What I need now is an explicit pointer - I know almost every var in ruby is a pointer, except Fixnums and Float (and maybe some other). Even though, the array gets to big, so I need a real pointer.

(I also tried to setup an array of object_ids and load them via ObectSpace, but sadly - because I often have to load the rooms - the rooms with the wanted object_id are already recycled then, as an error message explains.)

This is my recursive scan method:

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

Upvotes: 3

Views: 2569

Answers (4)

Andrew Grimm
Andrew Grimm

Reputation: 81500

A really hackish way to get all Rooms in memory would be:

all_rooms = ObjectSpace.each_object(Room).to_a

Upvotes: 1

Yossi
Yossi

Reputation: 12100

It is a classical graph problem. Using graph library will handle most of these issues. Try using the rgl gem.

Define each room as a vertex in the graph. The connections will be the edges.

require "rgl/adjacency"

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

Now you can test whether two rooms are directly connected in O(1):

map.has_edge? room1, room2

Or get the list of all rooms:

map.vertices

You can also get the list of all adjacent rooms:

map.adjacent_vertices(room)

Upvotes: 3

DigitalRoss
DigitalRoss

Reputation: 146053

Everything in Ruby is already a reference.

Why not just maintain a room index?

rooms[room.number] = room

Then you can get anything with rooms[i]. I would keep the index up to date incrementally by simply modifying the initialize method of Room.

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

This won't take up much space because the array is just an index, it doesn't actually have copies of the rooms. Each reference obtained from the array is essentially the same thing as a reference obtained via any other mechanism in your program, and the only real difference between the reference and a classic pointer is a bit of overhead for garbage collection.

If rooms are ever deleted (other than just before exit) you will want to set the rooms[x] = nil when on deletion.

I don't see why you need to create the data structure first and then index the rooms, but FWIW you should be able to do that recursive enumeration and use the rooms presence in the room index array as the been-here flag. I'm not sure why it didn't work before but it really has to if written carefully.

Upvotes: 6

bheeshmar
bheeshmar

Reputation: 3205

You may want to look at the NArray gem, which will speed up using arrays of numbers. You may be trying to force a square peg into a round hole here with this approach.

Upvotes: 0

Related Questions