3
\$\begingroup\$

I've been trying to formulate the question and try to find some information on Google, but didn't managed to, so here it is... We've got a nice tropic-themed game that is about to be released soon, that uses a tile map and an A* pathfinding is utilized and everything works flawlessly.

Until when it comes to the point where I need to somehow find unoccupied patch of area on the map that matches certain criteria, so that I can guide the player to place their just bought map objects on.

The map is 200x200 tiled map and it holds instances of each tile that determine two things - if it is occupied and if it is a water or a ground tile. These are already used for the A* pathfinding algorithm that I've put into the game.

Let's say the player buys a water-placible map object from the store and the map object occupies 5x5 tiles for instance. I need to guide the player to a free patch of water tiles where they can place that map object.

Any guidance and/or reference to such algorithms will be highly appreciated :) Thanks

EDIT: It turns out that I need to find such a patch as close as possible to given point (centre of viewport for instance). This will improve user experience

\$\endgroup\$
  • \$\begingroup\$ Will the objects all have rectangular areas, or will you also need to include irregularly shaped objects? And will you have objects that will be placeable partially on water, partially on land? I can think of an approach that would work for any situation, but it's a pretty brute-force approach, so it would help if you gave more specifics. \$\endgroup\$ – Fault Dec 8 '13 at 15:43
  • \$\begingroup\$ @Fault all the objects will have square areas, and there are no objects that are put partly on water and partly on land. I also have some suggestions but I wonder if there is definite algorithm for this. \$\endgroup\$ – Martin Asenov Dec 8 '13 at 15:56
4
\$\begingroup\$

Method 1 Here's a fairly brute-force algorithm:

  1. Scan across each row, left to right, top to bottom, until you hit an unoccupied tile of the correct type. (You can skip the far right columns/bottom rows once you get too close for the placement to fit)

  2. Once you find a valid tile, check all tiles that would be within the placement footprint, if you put the top left corner here. Start with the tile furthest away (the bottom-right corner of the placement), and gradually work back.

  3. If you find an invalid tile (wrong type/already occupied), mark all tiles in the rectangle containing your proposed top-left corner and the obstacle as "explored", and resume searching with the next tile after the proposed top-left corner.

  4. As you continue your main scan, skip over any tiles marked "explored"

  5. If your search in 2 does not find an obstacle, return your proposed top-left corner as a valid placement and terminate.

Steps 3 & 4 are a small improvement over straight-up brute force search, in that they keep you from repeatedly checking the same patch. Starting from the opposite corner lets you skip as many tiles as possible using this trick.

Method 2 If you need to improve on this (profile, to see if it's worth your trouble), you can keep a bit of helper data with each tile: the size of the largest unoccupied square of the same type with that tile as its top-left corner.

Fill this data in once during map generation, by brute force if need be, then update it any time a tile changes state (search a rectangle up & left of the changed tile for any tiles that count it in their largest square. Decrease their largest square so that it ends just before the changed tile. You can end this search early once you've gone as far as the widest placeable item in your game.)

Now you can find a rectangle of the right size with a linear scan of the map. You can shape this scan any way you want - say searching an expanding spiral out from the focus of the player's current view, so that you can minimize the camera move required.

If you need even faster lookups (doubtful), you can use this data to sort your tiles into a heap (or series of heaps) by largest-placeable-area. Then in a O(1) operation you can pluck out a tile big enough for a given placement, or correctly conclude that none exists. (Just watch out, if you always choose the biggest-available area, regardless of the size of the placement, you'll tend to fritter away your wide open space on small placements)

That kind of acceleration structure can be expensive to maintain though, so only do it if your searches for placeable areas are causing noticeable problems.

\$\endgroup\$
  • 1
    \$\begingroup\$ immediate +1 for the extensive answer :) I need to implement this and will tell the results once I've got them. Thank you \$\endgroup\$ – Martin Asenov Dec 9 '13 at 11:18
  • 1
    \$\begingroup\$ it works and is blazingly fast. I didn't expect that really.. Thought it would be laggy - the map is 300x300 actually. And it finishes in a blink of an eye. Thank you, answer accepted! \$\endgroup\$ – Martin Asenov Dec 9 '13 at 19:51
  • \$\begingroup\$ Glad to hear it! It's pretty amazing how quickly modern chips can chew through data, even with a fairly blunt algorithm, isn't it? :) If I may ask, which method did you decide to use? \$\endgroup\$ – DMGregory Dec 9 '13 at 22:22
  • 1
    \$\begingroup\$ The first one. I have a dynamic isometric map where objects can be moved and release previous positions and occupy new. So I decided to first try the more straightforward method, and, if it is not fast enough, try optimizing it. Fortunately, it proved to be fast enough. There is a slight lag due to that, but it is almost unnoticeable. \$\endgroup\$ – Martin Asenov Dec 12 '13 at 9:30
  • \$\begingroup\$ I need some more help, I'd be very glad if you assist me. Thanks \$\endgroup\$ – Martin Asenov Jan 31 '14 at 18:09
2
\$\begingroup\$

A similar problem is finding the largest square block in a binary matrix and the algorithm actually gives the number of largest square blocks for every cell if this cell is top-left of the square block.

A very good documentation of the algorithm is the answer by Joy Dutta in the Dynamic programming - Largest square block question on SO.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.