Lua Partition Algorithm grouping overlaps rooms at one corner

Question

I am trying to implement a dungeon generation algorithm ( presented here and demo-ed here ), which involves creating a random number of cells that overlap each other. Then the cells are repelled / separated and then connected. Now, the original poster / author has described that he uses the Split Separation Algorithm to evenly distribute cells across the area. I did not have much experience with the flocking algorithm and / or sharing control, so I turned to Google for an explanation (and found this ). My implementation (based on the last article) 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.."") vx = (vx + self._rooms[_agent].startX - self._rooms[i].startX) * distance vy = (vy + self._rooms[_agent].startY - self._rooms[i].startY) * distance neighbours = neighbours + 1 end end end if neighbours == 0 then return v else vx = vx / neighbours vy = vy / neighbours vx = vx * -1 vy = vy * -1 pdg:_normalize(v, 1) return v end end 

self._rooms is a table containing the starting position X and Y of the room in the grid, as well as the width and height (endX, endY).

The problem is that instead of placing cells in the grid neatly, it takes overlapping cells and moves them to the area that goes from 1.1 to distance + 2, distance + 2 ( as shown in my video [youtube] )

I am trying to understand why this is happening.

If necessary, here I parse the grid table, divide and fill the cells after 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 = vx self._rooms[i].startY = vy --self._rooms[i].endX = vx + self._rooms[i].endX --self._rooms[i].endY = vy + 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 also implemented this generation algorithm, and I ran into more or less the same problem. All my rectangles hit the top corner.

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

You can fix this by simply checking to see if your speed length is zero before using it for any further calculations.

Hope this helps!

Answer 2

I know this is an old question, but I noticed something and maybe it can be useful to someone, so ...

I think there is a problem here:

 vx = (vx + self._rooms[_agent].startX - self._rooms[i].startX) * distance vy = (vy + self._rooms[_agent].startY - self._rooms[i].startY) * distance 

Why do you multiply these equations by distance? " (self._rooms[_agent].startX - self._rooms[i].startX) " already contains (square) distance! Plus, multiplying everything by " distance ", you change your previous results stored in v! If at least you put "vx" outside the brackets, the result will only be higher, the normalization function will fix it. Although this useless calculation ...

By the way, I'm sure the code should look like this:

 vx = vx + (self._rooms[_agent].startX - self._rooms[i].startX) vy = vy + (self._rooms[_agent].startY - self._rooms[i].startY) 

I will give an example. Imagine that you have your main agent at (0,0) and three neighbors at (0, -2), (-2,0) and (0,2). The steering controls divide the main agent into the X axis in the normalized direction (1.0). Let it focus only on the Y-component of the result vector.

The math should be something like this:

 --Iteration 1 vy = 0 + ( 0 + 2 ) --Iteration 2 vy = 2 + ( 0 - 0 ) --Iteration 3 vy = 2 + ( 0 - 2 ) --Result vy = 0 

This is consistent with our theory. This is what your code does:

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

And if I got the correct separation behavior, it could not be right.