Jump to content

Room detection / floodfill algorithm in PhaserJS


s4m_ur4i
 Share

Recommended Posts

So, this one is a bit tricky I think. I have set up a grid (30x30).
And you can place "room" sprites ( w: 30, h: 30). They are all aligned to the grid. so their coords are 30,0 / 60, 0 etc.
A real room should be made out of a few "room" sprites.

now, I would like to detect if a room is at least made out of 3 by 3 sprites. Since you can have multiple rooms this has to be checked each time a sprite is placed.
I have been googling for some time now and read some answers in similar directions which are about floodfill algorithms.

Since my rooms are constant on coords and sprite w/h, i think, it can be a bit easier than this. Are there any suggestions
How this can be realized into phaserjs? Need some food for thought.


~happy new year to all of you.
regards :)

Link to comment
Share on other sites

Are you using tilemaps? (http://phaser.io/examples/v2/category/tilemaps)  Regarding flood fill, are you talking about a filling algorithm for the pixels themselves?

 

A 30x30 grid is essentially a 900 element array.  (For example, tile[x][y], where each dimension runs 0-29.)  With such an array in place, there are 9 different cases that satisfy the 3x3 room requirement.  (The initial tile checked could be one of nine different tiles in a minimum 3x3 room.)  Each of those nine cases share different tiles.  A series of if statements, although tedious, could easily determine which case fits, or if no cases fit.

 

If performance is very important, a secondary 2-dimensional array could be used to mark which tiles are part of "proper" rooms, versus only being basic room tiles.

 

Tom

Link to comment
Share on other sites

Hi Tom,

thanks for your replay:
 

 

 

If performance is very important, a secondary 2-dimensional array could be used to mark which tiles are part of "proper" rooms, versus only being basic room tiles.

This is really interesting, can you provide some really small example code? or visualization?

between I found this, and I think it is very interesting for everyone who comes across this thread:
FloodFill Algorithm in JS: https://github.com/hughsk/flood-fill

kind regards

Link to comment
Share on other sites

The attached image (tile_coloring_example.png) shows two arrays: a primary array and a secondary array.  The primary array records what type of tile was placed where.  This example has blank, or empty tiles, and room tiles.  The primary array can be checked every time a new room tile is placed to see if a 3x3 room has been constructed.  The secondary tile array records whether each tile is part of a "proper" room that is 3x3 or greater.  (In the diagram, tiles that are part of a proper room are labeled COMPLETE.)  The secondary array could be checked first, to see if an existing proper room is being grown, or if the new tile placed is potentially part of an entirely new proper room.

 

For small arrays that are updated infrequently, the secondary array may not be worth the effort to improve performance.  Simulations and certain AI algorithms are examples where the secondary array could be used to optimize performance. The secondary array also may be worthwhile if there are other factors such as room-based lighting, ceilings that show/hide, sound propagation algorithms, etc.

 

post-11220-0-62982800-1452272357.png

 

Tom

 

 

 

 

post-11220-0-62982800-1452272357.png

Link to comment
Share on other sites

 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...