Lua Separation Steering algorithm groups overlapping rooms into one corner

Question

I'm trying to implement a dungeon generation algorithm (presented here and demo-ed here ) that involves generating a random number of cells that overlap each other. The cells then are pushed apart/separated and then connected. Now, the original poster/author described that he is using a Separation Steering Algorithm in order to uniformly distribute the cells over an area. I haven't had much experience with flocking algorithm and/or separation steering behavior, thus I turned to google for an explanation (and found this ). My implementation (based on the article last mentioned) is as follows:

function pdg:_computeSeparation(_agent)
  local neighbours = 0
  local rtWidth = #self._rooms
  local v =
  {
    x = self._rooms[_agent].startX,
    y = self._rooms[_agent].startY,
    --velocity = 1,
  }

  for i = 1, rtWidth do
    if _agent ~= i then
      local distance = math.dist(self._rooms[_agent].startX, 
                                 self._rooms[_agent].startY, 
                                 self._rooms[i].startX,
                                 self._rooms[i].startY)
      if distance < 12 then
        --print("Separating agent: ".._agent.." from agent: "..i.."")
        v.x = (v.x + self._rooms[_agent].startX - self._rooms[i].startX) * distance
        v.y = (v.y + self._rooms[_agent].startY - self._rooms[i].startY) * distance
        neighbours = neighbours + 1
      end
    end
  end


  if neighbours == 0 then
    return v
  else
    v.x = v.x / neighbours
    v.y = v.y / neighbours
    v.x = v.x * -1
    v.y = v.y * -1
    pdg:_normalize(v, 1)
    return v
  end
end

self._rooms is a table that contains the original X and Y position of the Room in the grid, along with it's width and height (endX, endY).

The problem is that, instead of tiddly arranging the cells on the grid, it takes the overlapping cells and moves them into an area that goes from 1,1 to distance+2, distance+2 (as seen in my video [youtube])

I'm trying to understand why this is happening.

In case it's needed, here I parse the grid table, separate and fill the cells after the separation:

function pdg:separate( )
  if #self._rooms > 0 then
    --print("NR ROOMS: "..#self._rooms.."")

    -- reset the map to empty
  for x = 1, self._pdgMapWidth do
    for y = 1, self._pdgMapHeight do
      self._pdgMap[x][y] = 4
    end
  end

  -- now, we separate the rooms
  local numRooms = #self._rooms
  for i = 1, numRooms do
    local v = pdg:_computeSeparation(i)
    --we adjust the x and y positions of the items in the room table
    self._rooms[i].startX = v.x
    self._rooms[i].startY = v.y
    --self._rooms[i].endX = v.x + self._rooms[i].endX 
    --self._rooms[i].endY = v.y + self._rooms[i].endY
  end


  -- we render them again
  for i = 1, numRooms do
    local px = math.abs( math.floor(self._rooms[i].startX) )
    local py = math.abs( math.floor(self._rooms[i].startY) )

    for k = self.rectMinWidth, self._rooms[i].endX do
      for v = self.rectMinHeight, self._rooms[i].endY do
        print("PX IS AT: "..px.." and k is: "..k.." and their sum is: "..px+k.."")
        print("PY IS AT: "..py.." and v is: "..v.." and their sum is: "..py+v.."")
        if k == self.rectMinWidth or 
           v == self.rectMinHeight or 
           k == self._rooms[i].endX or 
           v == self._rooms[i].endY then
          self._pdgMap[px+k][py+v] = 1
        else
          self._pdgMap[px+k][py+v] = 2
        end
      end
    end
  end
end

Answer 1

I have implemented this generation algorithm as well, and I came across more or less the same issue. All of my rectangles ended up in the topleft corner.

My problem was that I was normalizing velocity vectors with zero length. If you normalize those, you divide by zero, resulting in NaN.

You can fix this by simply performing a check whether your velocity's length is zero before using it in any further calculations.

I hope this helps!

Answer 2

Uhm I know it's an old question, but I noticed something and maybe it can be useful to somebody, so...

I think there's a problem here:

v.x = (v.x + self._rooms[_agent].startX - self._rooms[i].startX) * distance
v.y = (v.y + self._rooms[_agent].startY - self._rooms[i].startY) * distance

Why do you multiply these equations by the distance? "(self._rooms[_agent].startX - self._rooms[i].startX)" already contains the (squared) distance! Plus, multiplying everything by "distance" you modify your previous results stored in v! If at least you put the "v.x" outside the bracket, the result would just be higher, the normalize function will fix it. Although that's some useless calculation...

By the way I'm pretty sure the code should be like:

v.x = v.x + (self._rooms[_agent].startX - self._rooms[i].startX)
v.y = v.y + (self._rooms[_agent].startY - self._rooms[i].startY)

I'll make an example. Imagine you have your main agent in (0,0) and three neighbours in (0,-2), (-2,0) and (0,2). A separation steering behaviour would move the main agent toward the X axis, at a normalized direction of (1,0). Let's focus only on the Y component of the result vector.

The math should be something like this:

--Iteration 1
v.y = 0 + ( 0 + 2 )
--Iteration 2
v.y = 2 + ( 0 - 0 )
--Iteration 3
v.y = 2 + ( 0 - 2 )
--Result
v.y = 0

Which is consistent with our theory. This is what your code do:

(note that the distance is always 2)
--Iteration 1
v.y = ( 0 + 0 + 2 ) * 2
--Iteration 2
v.y = ( 4 + 0 - 0 ) * 2
--Iteration 3
v.y = ( 8 + 0 - 2 ) * 2
--Result
v.y = 12

And if I got the separation steering behaviour right this can't be correct.