# Reducing Collision Checks

This topic is 823 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello forum!

I'm currently trying to minimise collision checking.

The mouse clicks and my program checks whether it did hit a bunch of 2d triangles.

The red point represents the 1px thick click. Two triangles form the upper and lower part of a tile.

Easiest solution: I could bruteforce through all triangles until I find one that contains the click.

My "improvement": I check on whether which square of a tile the mouse click is near to. By dividing the mouse click's coordinates and mapping them to the grid.

Via this way, I find the blue square on the photo. What I can do now, is looking at the IEEE numbers and ceiling() floor() them, to find potential tiles.

These are the white ones. I would have to check the black one, upper and lower part (in this case, I found it after checking the upper one), and the halves of the upper white ones (coloured purple and cut-off by blue).

The grey ones are just to show the continuation of the grid.

However, I feel like this way is inefficient and maybe too complex already?

##### Share on other sites

If the triangles are effectively a uniform grid I don't see why you can directly map XY coordinates to grid diamonds. I guess it depends on how you are actually representing the tiles in memory, if they are being rendered as a grid with every other row offset by half the size of a tile then it should be simple enough to directly determine exactly what tile is there.

You would first determine what row, by dividing by the vertical size of the tiles, and then if it's even/odd you know the X index has 0 or 1 added to it, depending on whether the first or second row is offset first, then just take the X coordinate of the click (divided by X size of a tile) and add it to the row-odd/even offset to get the columnar index of the tile.

EDIT: Actually, you will need to incorporate a manhattan distance check against the center of the tile's index to determine further XY offsets to the indexing since the shape is a diamond.

Edited by deftware

##### Share on other sites

Easiest solution: I could bruteforce through all triangles until I find one that contains the click.

is there something wrong with this approach? have you tried it and its too slow? or are you engaging in mental premature optimization here?

always try brute force first, unless you already know it won't work.

##### Share on other sites

Since a triangle can be represented as a composition of smaller triangles you could use an approach similar to a quad tree.

Create a tree data structure where each parent represents a triangle and its children represent the four smaller triangles that make up their parent. To traverse the tree you'd use a point_in_triangle function and traverse down it similar to how you'd traverse a quad tree.

I am making some assumptions here based on your screenshot. Namely that your triangles are the same size. If your scene was contained within some arbitrary polygon your data structure would be a bit more complex but still similar.

Edited by DishSoap

1. 1
2. 2
3. 3
Rutin
13
4. 4
5. 5

• 26
• 11
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633697
• Total Posts
3013407
×