6
\$\begingroup\$

Here is what I am trying to implement. I wrote a script that allows the player to place walls during run-time, in non grid-based 3D environment (walls can be diagonal with rotation increasing/decreasing in amounts of 10 degrees). Like the figure below shows, since wall can form different angles, rooms might end up having both convex and concave angles:

enter image description here

What I have been looking for, without success so far, is a way to detect in which room a given character is, according to its position. Of course, if that was a grid-based setting, I could only pass an ID for each cell and then retrieve the ID of the cell where the given character stands. However, that being a non-grid setting and with irregular rooms that have shapes unknown in advance, how could I accomplish that in an efficient way?

Many thanks.

EDIT: Although it is a 3D environment, the problem may be treated as a 2D one since height is not a concern here.

\$\endgroup\$
6
  • 3
    \$\begingroup\$ Is it ok to drop the z coordinate and treat it as a 2D problem? If so point in polygon is straight forward. \$\endgroup\$
    – Steven
    Commented Oct 20, 2015 at 20:28
  • \$\begingroup\$ Also don't see a figure showing up. \$\endgroup\$
    – Steven
    Commented Oct 20, 2015 at 20:28
  • \$\begingroup\$ Do you know which walls form a which room? (= do you know the polygon "shape" of each room?) \$\endgroup\$
    – wondra
    Commented Oct 20, 2015 at 20:31
  • 1
    \$\begingroup\$ Do you have constraints when the rooms are built that they have distinct doors or portals between them? \$\endgroup\$
    – Steven
    Commented Oct 20, 2015 at 20:34
  • \$\begingroup\$ Sorry for the figure, now it's showing up. So, @Steven, good point: it is totally ok to treat as a 2D problem. I will even edit to make that mention. Also, the only constrains about doors is that each room has to have at least one door. The rest is unconstrained. \$\endgroup\$
    – MAnd
    Commented Oct 20, 2015 at 20:37

2 Answers 2

Reset to default
6
\$\begingroup\$

I think the easiest thing would be to solve it as a 2 dimensional problem. Further, if the constraints are such that each room must be 'closed' then it turns into a point-in-polygon problem, which is easy to solve - essentially a test is performed whereby a segment from the point to some infinite distance is tested against each segment of the polygon. If the number of times the ray crosses segments is odd, the point is inside the polygon. If it is even, the point is outside the polygon. There's already an answer here: https://stackoverflow.com/questions/217578/point-in-polygon-aka-hit-test

As noted by Wondra's comment & answer, it may be more bullet proof to use the signed winding number method instead, which handles self intersecting polygons and polygons with whole inside them. There is a C++ implementation is found here: http://geomalgorithms.com/a03-_inclusion.html

You just need to track the polygon's vertices as the room is created for this to work.

The other thing you'll want to do is to take each room's minimum and maximum points to create an axis aligned bounding box. Prior to testing a room's polygon, test if the player's point is inside the bounding box. If it is not, then there is no point doing further tests for that room. Point-in-AABB 2D is very fast - check if Point.x is >= AABB.min.x and Point.X <= AABB.max.x, and the same for point.Y. This will greatly increase the performance of your search.

Finally, if you have a lot of rooms, you will want to organize your AABBs into a spatial structure to speed that up even more - either a grid, quad-tree or balanced AABB tree (look at Box2D's broadphase for this one - dynamic bounding volume).

As Loren Pechtel outlined in his comment, the grid would store a linked list in each cell of the rooms that overlap the cell. Then you could use the player's position to lookup the cell, which would then have a linked list of the rooms to test. When in the middle of a room you would have only one item in the grid-cell's list. This could be the fastest approach for spatial partitioning if the balance of grid size and room size is correct.

Good luck

\$\endgroup\$
17
  • \$\begingroup\$ Great idea to combine both spatial partitioning and point in polygon +1. I would like to point out that crossing number cannot handle some convex polygons(self-intersecting to be more precise, but that probably will not be issue here), winding number handles all of them and it is as fast as cn. \$\endgroup\$
    – wondra
    Commented Oct 20, 2015 at 21:01
  • \$\begingroup\$ @wondra You are correct - I assumed crossing number would be enough - but you are right a more aggressively testing might be worth the effort since the content is user created. \$\endgroup\$
    – Steven
    Commented Oct 20, 2015 at 21:06
  • \$\begingroup\$ Since the problem space is rooms a self-intersecting polygon makes no sense. You can't put a wall inside a wall--if it's permitted at all it should divide the space into multiple rooms instead of permitting a convex, self-intersecting polygon. \$\endgroup\$
    – Loren Pechtel
    Commented Oct 21, 2015 at 3:59
  • \$\begingroup\$ Another way of organizing rooms for fast searching: Lay a grid over your space. Each grid cell has a linked list of the rooms that appear within that grid cell, you only need to test a point against the rooms in it's grid cell. This is pretty close to O(1), rather than the O(log n) of trees. \$\endgroup\$
    – Loren Pechtel
    Commented Oct 21, 2015 at 4:01
  • \$\begingroup\$ Great answer, @Steven! That's a nice idea. I will give it a try tomorrow, using the winding method. I specially like the spatial partitioning idea and quick AABB check. About the later, what if all the building is Y-rotated? I though of the following. Since the whole problem can be boiled down to 2D as you've asked before, wouldn't it be simpler to transform the character position and the position of the vertices of rooms-polygons to a local space (let's say of the yellow object representing the whole building floor) and then do the check you suggest (char.x >= min.x && char.x <= max.x)? \$\endgroup\$
    – MAnd
    Commented Oct 21, 2015 at 4:21
8
\$\begingroup\$

To test whether a point lies inside of polygon you have some options, best known crossing number algorithm or more "stable" winding algorithm(there is pretty fast implementation too).
Alternatively, you can also use some of spatial partitioning algorithms too, most notably BSP-type. While spatial partitioning will probably offer superior query performance, it will require dynamic updating structure(if rooms can be changed later) - there are dynamic variations of those algorithms, but it will be significantly harder to implement.

\$\endgroup\$
1
  • \$\begingroup\$ That was awesome that you brought the winding approach. Thanks! I will give it a try. \$\endgroup\$
    – MAnd
    Commented Oct 21, 2015 at 4:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .