[SOLVED] box2d categories + masks problem

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
User avatar
adnzzzzZ
Party member
Posts: 305
Joined: Sun Dec 26, 2010 11:04 pm
Location: Porto Alegre, Brazil

[SOLVED] box2d categories + masks problem

Post by adnzzzzZ » Thu Nov 07, 2013 12:14 am

The problem is that I have been using the following structure to define categories and masks of objects in my game:

Image

As you can see, it's getting kinda big with lots of numbers there, and the maximum number of different categories you can have is 16. While that won't happen any time soon, I'd be at peace if I could figure out a way of not having to deal with those categories and masks directly and to be able to define what should ignore what in a nicer way. The nicer way I have in mind is:

a)

Code: Select all

A.ignores = {'A', 'B', 'C', 'D'}
B.ignores = {'C'}
C.ignores = {'B'}
D.ignores = {'A', 'C', 'D'}
and automagically something like this would be generated:

b)

Code: Select all

collision_masks['A'] = collision_mask({1}, {1, 2, 3, 4})
collision_masks['B'] = collision_mask({2}, {3})
collision_masks['C'] = collision_mask({3}, {2})
collision_masks['D'} = collision_mask({4}, {1, 3, 4})
This example looks obvious, so I thought it was going to be easy to translate this into a nice simple algorithm. But it's actually really hard and I don't know how to do it. Does anyone have any ideas?

tldr: need help creating an algorithm that translates a) into b) while using the least number of categories possible (so the 16 limit isn't reached).

The structures (collision_mask(s), .ignores, and other tables) are meaningless, I'm interested in a high level description of an algorithm to solve this. Or just another completely different way of handling categories + masks with box2d, that would work too.
Last edited by adnzzzzZ on Thu Nov 07, 2013 5:35 pm, edited 1 time in total.

Wojak
Party member
Posts: 134
Joined: Tue Jan 24, 2012 7:15 pm

Re: box2d categories + masks problem

Post by Wojak » Thu Nov 07, 2013 11:11 am

like this?
http://luachunks.com/chunk/Li16vdhB91

Code: Select all

local A,B,C,D = {},{},{},{}
local id = {A=1,B=2,C=3,D=4}
A.name="A"
A.ignores = {'A', 'B', 'C', 'D'}
B.name="B"
B.ignores = {'C'}
C.name="C"
C.ignores = {'B'}
D.name="D"
D.ignores = {'A', 'C', 'D'}
local allstuff = {A,B,C,D}
local collision_masks = {}
function collision_mask()
    --dumy
end
for i,stuff in pairs(allstuff) do
    local tab = {}
    local tabdraw=""
    for j=1,#stuff.ignores do
    
        tab[#tab+1]=id[stuff.ignores[j]]
        tabdraw = tabdraw..id[stuff.ignores[j]]..","
    end
    
    print("collision_masks['"..stuff.name.."'] = collision_mask({"..id[stuff.name].."}, {"..tabdraw.."})")
    collision_masks[stuff.name]=collision_mask({id[stuff.name]},tab)
end

User avatar
adnzzzzZ
Party member
Posts: 305
Joined: Sun Dec 26, 2010 11:04 pm
Location: Porto Alegre, Brazil

Re: box2d categories + masks problem

Post by adnzzzzZ » Thu Nov 07, 2013 11:48 am

... no.
The structures (collision_mask(s), .ignores, and other tables) are meaningless, I'm interested in a high level description of an algorithm to solve this.
You manually inserted the ids, I want an algorithm that automatically generates them...

Wojak
Party member
Posts: 134
Joined: Tue Jan 24, 2012 7:15 pm

Re: box2d categories + masks problem

Post by Wojak » Thu Nov 07, 2013 12:04 pm

one last tty...
http://luachunks.com/chunk/Li16vdhB91

Code: Select all

local A,B,C,D = {},{},{},{}
local id = {}
A.name="A"
A.ignores = {'A', 'B', 'C', 'D'}
B.name="B"
B.ignores = {'C'}
C.name="C"
C.ignores = {'B'}
D.name="D"
D.ignores = {'A', 'C', 'D'}
local allstuff = {A,B,C,D}
local collision_masks = {}
function collision_mask()
    --dumy
end
for i=1,#allstuff do
    id[allstuff[i].name]=i
end
for i=1,#allstuff do
    stuff = allstuff[i]
    local tab = {}
    local tabdraw=""
    for j=1,#stuff.ignores do
    
        tab[#tab+1]=id[stuff.ignores[j]]
        tabdraw = tabdraw..id[stuff.ignores[j]]..","
    end
    
    print("collision_masks['"..stuff.name.."'] = collision_mask({"..id[stuff.name].."}, {"..tabdraw.."})")
    collision_masks[stuff.name]=collision_mask({id[stuff.name]},tab)
end

User avatar
adnzzzzZ
Party member
Posts: 305
Joined: Sun Dec 26, 2010 11:04 pm
Location: Porto Alegre, Brazil

Re: box2d categories + masks problem

Post by adnzzzzZ » Thu Nov 07, 2013 12:11 pm

No. What happens when you have more than 16 different object types? You're simply using a new number for each one of them and it's not a solution.

For instance, the example pic of my game, doing what you're doing:

Code: Select all

Player = ({1}, {})
Solid = ({2}, {})
BreakableSolid = ({3}, {})
EnemyWall = ({4}, {1, 2, 3, 4, 7, 18, 19})
MeleeArea = ({5}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19})
PhysicsParticle = ({6}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17})
FaderParticle = ({7}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17})
BreakableParticle = ({8}, {1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 18})
Blaster = ({9}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17, 19})
Roller = ({10}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17, 19})
Item = ({11}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17})
SpikedBall = ({12}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17})
Spikes = ({13}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17})
Ladder = ({14}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17})
JumpingPad = ({15}, {})
ChainedSpikedBall = ({16}, {})
ChainedSpikedBallBall = ({17}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18})
TNT = ({18}, {})
Boulder = ({19}, {})
And as you can see, that goes over 16 categories.

User avatar
markgo
Party member
Posts: 189
Joined: Sat Jan 05, 2013 12:21 am
Location: USA

Re: box2d categories + masks problem

Post by markgo » Thu Nov 07, 2013 5:21 pm

1. Make a list of your categories and assign a number to each one
2. Do like part (a) except as you go down your list, do not assign pairs of previous categories
3. At the end, use a for loop to fill in the missing categories

Code: Select all

-- Pseudocode
A = {1=A,2=B,3=C,4=D}
B = {3=C}
C = {}
D = {4=D}

for letter,masks in categories do
	local current_num = ...
   for num,other_letter in masks do
      if num > current_num then
         local other_masks = categories[other_letter]
         other_masks[current_num] = letter
      end
	end
end

User avatar
sharpobject
Prole
Posts: 44
Joined: Fri Mar 18, 2011 2:32 pm
Location: California
Contact:

Re: box2d categories + masks problem

Post by sharpobject » Thu Nov 07, 2013 5:39 pm

We talked about this on IRC and stuff.

The question posed is, if each object type has a list of other object types that should be in its mask set, how can we classify the object types into the minimal number of categories? Two object types can belong to the same category if they always appear together in mask sets (so, X and Y can be in a category together if every mask set contains both or neither).

We can think of the input as a directed graph, where the vertices are object types and the edge (X,Y) exists iff Y is in X's mask set. The property "Two objects always appear together in mask sets" then becomes "For these two vertices X and Y, the set of vertices with edges to X is the same as the set of vertices with edges to Y."

Here is a solution using this fact. It computes a representation of these sets and builds categories from them.

Code: Select all

json = require"dkjson"

graph = {{{1}, {}},
{{2}, {}},
{{3}, {}},
{{4}, {1, 2, 3, 4, 7, 18, 19}},
{{5}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19}},
{{6}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17}},
{{7}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17}},
{{8}, {1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 18}},
{{9}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17, 19}},
{{10}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17, 19}},
{{11}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17}},
{{12}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17}},
{{13}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17}},
{{14}, {1, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17}},
{{15}, {}},
{{16}, {}},
{{17}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18}},
{{18}, {}},
{{19}, {}},}

function arr_to_set(t)
  local ret = {}
  for _,v in ipairs(t) do ret[v] = true end
  return ret
end

function set_to_arr(t)
  local ret = {}
  for k,_ in pairs(t) do ret[#ret+1] = k end
  table.sort(ret)
  return ret
end

function mapt(f, t)
  local ret = {}
  for i=1,#t do
    ret[i] = f[t[i]]
  end
  return ret
end

local incoming_strs = {}
for i=1,#graph do
  incoming_strs[i] = ""
end
for idx,node in ipairs(graph) do
  local out_edges = arr_to_set(node[2])
  for i=1,#graph do
    incoming_strs[i] = incoming_strs[i] ..
      (out_edges[i] and "flat girls" or "are the best")
  end
end

local equivalence_classes = {}
local old_to_new_label = {}
local nequiv = 0
for i=1,#graph do
  local label = incoming_strs[i]
  if not equivalence_classes[label] then
    nequiv = nequiv + 1
    equivalence_classes[label] = nequiv
  end
  old_to_new_label[i] = equivalence_classes[label]
end

new_graph = {}

for i=1,#graph do
  new_graph[i] = {mapt(old_to_new_label, graph[i][1]),
    set_to_arr(arr_to_set(mapt(old_to_new_label, graph[i][2])))}
end

print(json.encode(new_graph))

--[[
prints no-whitespace json equivalent of
{{{1},{}},
 {{2},{}},
 {{2},{}},
 {{3},{1,2,3,6}},
 {{4},{1,2,3,4,5,6}},
 {{4},{1,4}},
 {{3},{1,4}},
 {{4},{1,3,4}},
 {{4},{1,4,6}},
 {{4},{1,4,6}},
 {{4},{1,4}},
 {{4},{1,4}},
 {{4},{1,4}},
 {{4},{1,4}},
 {{4},{}},
 {{5},{}},
 {{4},{1,2,3,4,5}},
 {{3},{}},
 {{6},{}}}
--]]

User avatar
adnzzzzZ
Party member
Posts: 305
Joined: Sun Dec 26, 2010 11:04 pm
Location: Porto Alegre, Brazil

Re: [SOLVED] box2d categories + masks problem

Post by adnzzzzZ » Thu Nov 07, 2013 6:10 pm

sharpobject solved the problem and this was his solution: http://pastie.org/8462809#95. To add to his explanation, I'm gonna use a few examples and pictures to explain the solution at a high level. The first example will have this as input:

Code: Select all

A ignores A, B, C, D
B ignores C
C ignores D
D ignores A, C, D
First, generate a graph with one node for each different object type (in this case 4 nodes: A, B, C, D) and directed edges connecting nodes that ignore each other. The graph for this example looks like this:

Image

Now for each node, see which nodes its incoming edges come from. A has edges coming from A, D; B has edges coming from A, C; C has edges coming from A, B, D; D has edges coming from A, C, D. Then, for each one of those groups of edges (groups with same edges are counted as one, and the current groups are: (A, D), (A, C), (A, B, D) and (A, C, D)) create a new category. In this case, since all groups of edges are different, we create 4 categories.

Then set the category of that group to the corresponding node, so A will have category 1, B 2, C 3, D 4. And now we can set the masks appropriately too, since all category numbers are defined. So, in this case: A has category 1 and masks 1, 2, 3, 4; B has category 2 and masks 3; C has category 3 and masks 2; D has category 4 and masks 1, 3, 4.

This example doesn't illustrate the main issue of the problem though, which happens when we have the possibility of not using as many categories as there are objects, such as this:

Code: Select all

A ignores A, B, C
B ignores A, B, C
C ignores D
D ignores A, C, D
E ignores B, D
The graph looks like this:

Image

So, check all the incoming egdes and we have: A with A, B, D; B with A, B, E; C with A, B, D; D with C, D, E; E with nil. The groups are: (A, B, D), (A, B, E), (C, D, E), nil, which means that we create 4 categories.

So, A has category 1, B has category 2, C has category 1 (since it has the same incoming edges as A), D has category 3 and E has category 4. In this example we have 5 object types and 4 categories. So now we have some category reuse, which is what I wanted from the start! So for more complex examples (like the one sharpobject used up there), it starts being useful to have this algorithm set the category and mask numbers for you instead of having to do it manually. :crazy:

Thanks, sharpobject. Tharpobject.

szensk
Party member
Posts: 155
Joined: Sat Jan 19, 2013 3:57 am

Re: [SOLVED] box2d categories + masks problem

Post by szensk » Fri Nov 08, 2013 10:18 am

thank you for documenting your solution.

Post Reply

Who is online

Users browsing this forum: No registered users and 7 guests