Looking for research materials for multiple shape id interactivity

[tripdragon]

I have a grid with rows and columns of shapes. If I select a shape I get its id, but I now need to get an array of surrounding ids and shapes.

Presently I have in sudo code here:

let w_ = id 52

let r_ = row selected, count() number of columns in row

calculated_offset = w_ - r_.count

calculated_offset = 41

 

So essentially it can get an index and do offsets to make a mini grid. But this is so primitive to me.

If I want to calculate pi as the offset marker I could mash that into the primitive style.

offset_count = length + pi / radial space of grid item

 

The other way I was thinking is get id.x & y

ray cast 6 rays from id in pi, get length test against present known shapes location array

 

OH, could keep an array of shapes as they are built, for each move they update they're distance from each other in a chain and just ask for distance away, but that would be a long chain lookup, which might be fine and fast enough.

 

Hmmmm might have to build a mini 3d mesh editing app to get into this.

 

Anyway, the question was might you know of some cool links to read regarding this, does not matter the framework or lang. Its the system in thinking and battle terminology that matters.

 

 

 

 

[Deban]

I'm sorry, I don't really understand (specially the pseudo code).

 

Where you have the grid? What does it represent? How do you code that grid?

 

 

I will try to help, but probably it won't be really useful (with the 3d mesh you completely lost me).

This are examples to give you ideas, change it as you see fit.

 

The grid code:

var grid = [];var rowsAmount = 10;var colsAmount = 10;for (var x = 0; x < rowsAmount; x++) {    grid[x] = [];        for (var y = 0; y < colsAmount; y++) {        grid[x][y] = new Shape(/*Chose type here*/, x, y);    }}

 

The shape constructor:

function Shape (type, x, y) {    this.type = type;    this.id = ++Shape.lastID || 0;        this.position = {x: x, y: y};}

And lastly getting the shape and it's surrounding shapes:

var selectedShape = grid[selectedRow][selectedColum];var id = selectedShape.id;//The surrounding shapesvar surroundingShapes = [];//How many shapes I will select on each size, it's like a radius but the figure of the selection is a square.var sizeOfSelection = 4;//Current positionvar posX = selectedShape.position.x;var posY = selectedShape.position.y;for (var xOffset = -sizeOfSelection; xOffset <= sizeOfSelection; xOffset++) {    for (var yOffset = -sizeOfSelection; yOffset <= sizeOfSelection; yOffset++) {                surroundingShapes.push(grid[posX+xOffset][posY+yOffset]);    }}

Without knowing how you implement things, I can't help you much more.

[tripdragon]

Cool, thank you this will help others later on as well! However I did not want to entice you to submit code, thats my job. I'm more looking for materials to read and research of various implementations strategies so I can build the code.

I've now seen octree and quadtree as well as hashtree Kinetic.js does not have a good multi collision system built in from what I read in SO and the docs themselves.

[Deban]

Octree and quadtree are the same thing, the former is a 3D implementation of the last one.

 

Let's see... For what I understood, you use the shapes to check if they collide.

Collisions are divided in 2 phases. The broad phase and the narrow phase.

 

The broad phase is checking what can possible collide, the idea is to avoid using a free 4 all check (everything with everything). The common way to do this is by spatial partition, dividing the space in sectors.

In 2D the common approaches are: a common grid (also called hash table), a quadtree, binary space partition and sweep and prune.

Spatial partition means getting everything that is in a zone, or even near a zone. You can use this algorithms even if you are not checking for collisions.

Which algorithm to use, is heavily based in your game, how many objects you have, how much they move around, it's an open zone or a closed one, etc...

Here is an excellent article on hash table to get you started.

 

 

The narrow phase is checking if the objects that can collide actually do it. It's the common collision algorithm. Some people divide this in two steps, first a fast but inaccurate test to narrow the possibilities, even more, and then a expensive but exact algorithm.

The algorithms are (in order of complexity, accuracy and inverse speed):

• Circles. The most basic, the distance between the centre points of the circle should be less than the sum of the radius for the circles to collide.
• Axis Aligned Box (AAB). Which is a rectangle that can't rotate.
• Oriented Bounding Box (OBB). A rotated rectangle.
• Separating Axis Test (SAT). This is where you start to get a lot of control. You can use any polygon to test against any other polygon. The more faces, the slowest it becomes.
• Minkowski Difference. This is a different way to solve the same as SAT. You can use multiple polygons checks. Choose this or SAT based on which one you understand most.

This page contains all the algorithms except SAT. For SAT you can look here.

[tripdragon]

THIS!!! Thats the type of info I was seeking! The one golden rule i know of the world is know the technical terms and the world opens up. Thank you!