[SOLVED] box2d categories + masks problem

[adnzzzzZ]

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

dY10xYh.png (45.78 KiB) Viewed 446 times

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.

[Wojak]

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

[adnzzzzZ]

... 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]

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

[adnzzzzZ]

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.

[markgo]

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

[sharpobject]

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},{}}}
--]]

[adnzzzzZ]

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:

FCgSADx.png (14.01 KiB) Viewed 447 times

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:

kQ2jpwy.png (14.9 KiB) Viewed 447 times

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.

Thanks, sharpobject. Tharpobject.

[szensk]

thank you for documenting your solution.