Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 05 May 2013
Offline Last Active Sep 17 2014 02:24 AM

#5180412 Algorithm to find neighboring rectangles?

Posted by on 15 September 2014 - 03:28 AM

I have a huge rectangular region that I divided up into smaller rectangles. I used a binary space partitioning algorithm to do this task (details can be found at http://doryen.eptalys.net/articles/bsp-dungeon-generation/, up until 'Building the dungeon'). However, after dividing up the space, I want to, for each individual rectangle leaf in the tree, determine all the rectangle leaves that share an edge, or any part of an edge, with it (obviously, this will always include that leaf's sibling, but may also include other nodes that could very well be on the other side of the tree). For example, in the picture http://doryen.eptalys.net/data/articles/dungeon_bsp3-medium.jpg, the rectangle in the upper left corner is neighbored by the rectangles directly east, south, and southeast of it. Assuming that I can use the list of rectangle leaves without considering the structure of the underlying tree or work directly on the tree (possibly as it's being built?), whichever works best, does anyone have any ideas as to an efficient algorithm to perform this task faster than simply checking all pairs of rectangles?

#5059819 A* pathfinding around axis-aligned rectangle obstacles

Posted by on 06 May 2013 - 02:25 PM

Hmm, it certainly sounds like I can reduce the running time by calculating connections while pathfinding rather than before, as you guys said.

Perhaps I should have mentioned some more details: the player character walks around a 2D area with rectangle obstacles that don't move (or rather, very few obstacles are able to move around, and they're always player-sized or smaller, so if we collide with something, we can just run the pathfinding again). The reason why I said that the rectangles move around a lot is that the player can only see a certain area of the map (which is huge), and because the player is constantly moving whenever it paths around, rectangles move around, get placed in the area of sight, fall out of the area of sight, etc, all the time. However, while pathfinding, they're definitely mostly stationary. The player is the only agent that needs to pathfind. Also, when I pathfind, I'm only looking to go from the starting point to wherever I want to go to, no more. The environment to path in is typically medium-sized (I know that's a poor description but I'm not sure how else to explain it). Also, the rectangle obstacles are allowed to overlap each other, which I hope will not affect the algorithm (at least, it doesn't seem to me like it should affect a great deal).

There's also something else I should have added. Sometimes, it's not possible to find a path from A to B (ie, when B is inside an obstacle or enclosed by rectangle obstacles). Would I have to search through all points, then?