java - Find inside coordinates of polygon in tile based map -
if have of outer edges of polygons in list how go finding inside coordinates?? make matters simple drew following image represent problem:
i need find inside of 'buildings' in tilebased game.
- outside walls - grey shaded cells.
- inside building - light blue cells.
in event building not shown in view (right building) have solved issue adding entire green section (-1,-1, 0,-1, etc.) list.
without following insane if search tree have no idea how solve this. posting here tips, code, or psuedo code. appreciated. much! :)
edit
@andrew thompson: think miswrote situaton. not duplicate linked to. don't have image. excel drawing did above example. example:
i have list containing brown values: ie. {"1,1", "2,1", "3,1", "1,2", etc.}
and need corresponding list of blue values: ie. {"2,2", "2,6", "3,6", "4,6", etc.}
i toyed around a* algorithm week. there may other solutions request, since have code, matter of adapting needs. however, specific requirement use primitive flood-fill algorithm , classify cells way, see method in algorithm code.
the a* algorithm finds path given start given goal. in case start goal, means it's reference point classifies "outside" cell. there on search can traverse.
i left path finding code in example, maybe it's of use further needs.
here's code:
demo.java
import java.util.list; import java.util.set; public class demo { public static void main(string[] args) { // create grid in example int cols = 9; int rows = 9; grid grid = new grid( cols, rows); // create walls in example grid.getcell( 1, 1).settraversable( false); grid.getcell( 2, 1).settraversable( false); grid.getcell( 3, 1).settraversable( false); grid.getcell( 1, 2).settraversable( false); grid.getcell( 3, 2).settraversable( false); grid.getcell( 6, 2).settraversable( false); grid.getcell( 7, 2).settraversable( false); grid.getcell( 8, 2).settraversable( false); grid.getcell( 1, 3).settraversable( false); grid.getcell( 2, 3).settraversable( false); grid.getcell( 3, 3).settraversable( false); grid.getcell( 6, 3).settraversable( false); grid.getcell( 6, 4).settraversable( false); grid.getcell( 7, 4).settraversable( false); grid.getcell( 1, 5).settraversable( false); grid.getcell( 2, 5).settraversable( false); grid.getcell( 3, 5).settraversable( false); grid.getcell( 4, 5).settraversable( false); grid.getcell( 5, 5).settraversable( false); grid.getcell( 7, 5).settraversable( false); grid.getcell( 8, 5).settraversable( false); grid.getcell( 1, 6).settraversable( false); grid.getcell( 5, 6).settraversable( false); grid.getcell( 1, 7).settraversable( false); grid.getcell( 2, 7).settraversable( false); grid.getcell( 3, 7).settraversable( false); grid.getcell( 4, 7).settraversable( false); grid.getcell( 5, 7).settraversable( false); // find traversables // ------------------------- astaralgorithm alg = new astaralgorithm(); cell start; cell goal; // reference point = 0/0 start = grid.getcell(0, 0); set<cell> visited = alg.getfloodfillcells(grid, start, true); // find inside cells for( int row=0; row < rows; row++) { for( int col=0; col < cols; col++) { cell cell = grid.getcell(col, row); if( !cell.traversable) { cell.settype(type.wall); } else if( visited.contains( cell)) { cell.settype(type.outside); } else { cell.settype(type.inside); } } } // log inside cells for( int row=0; row < rows; row++) { for( int col=0; col < cols; col++) { cell cell = grid.getcell(col, row); if( cell.gettype() == type.inside) { system.out.println("inside: " + cell); } } } // path finding // ------------------------- // start = top/left, goal = bottom/right start = grid.getcell(0, 0); goal = grid.getcell(8, 8); // find a* path list<cell> path = alg.findpath(grid, start, goal, true); // log path system.out.println(path); system.exit(0); } } type.java
public enum type { outside, wall, inside, } cell.java
public class cell implements cloneable { int col; int row; boolean traversable; type type; double g; double f; double h; cell camefrom; public cell( int col, int row, boolean traversable) { this.col=col; this.row=row; this.traversable = traversable; } public double getf() { return f; } public double getg() { return g; } public double geth() { return h; } public void settraversable( boolean traversable) { this.traversable = traversable; } public void settype( type type) { this.type = type; } public type gettype() { return this.type; } public string tostring() { return col + "/" + row; } } grid.java
public class grid { cell[][] cells; int cols; int rows; public grid( int cols, int rows) { this.cols = cols; this.rows = rows; cells = new cell[rows][cols]; for( int row=0; row < rows; row++) { for( int col=0; col < cols; col++) { cells[row][col] = new cell( col, row, true); } } } public cell getcell( int col, int row) { return cells[row][col]; } /** * neighboring cells relative given cell. default top/right/bottom/left. * if allowdiagonals enabled, top-left, top-right, bottom-left, bottom-right cells in results. * @param cell * @param allowdiagonals * @return */ public cell[] getneighbors(cell cell, boolean allowdiagonals) { cell[] neighbors = new cell[ allowdiagonals ? 8 : 4]; int currentcolumn = cell.col; int currentrow = cell.row; int neighborcolumn; int neighborrow; // top neighborcolumn = currentcolumn; neighborrow = currentrow - 1; if (neighborrow >= 0) { if( cells[neighborrow][neighborcolumn].traversable) { neighbors[0] = cells[neighborrow][neighborcolumn]; } } // bottom neighborcolumn = currentcolumn; neighborrow = currentrow + 1; if (neighborrow < rows) { if( cells[neighborrow][neighborcolumn].traversable) { neighbors[1] = cells[neighborrow][neighborcolumn]; } } // left neighborcolumn = currentcolumn - 1; neighborrow = currentrow; if ( neighborcolumn >= 0) { if( cells[neighborrow][neighborcolumn].traversable) { neighbors[2] = cells[neighborrow][neighborcolumn]; } } // right neighborcolumn = currentcolumn + 1; neighborrow = currentrow; if ( neighborcolumn < cols) { if( cells[neighborrow][neighborcolumn].traversable) { neighbors[3] = cells[neighborrow][neighborcolumn]; } } if (allowdiagonals) { // top/left neighborcolumn = currentcolumn - 1; neighborrow = currentrow - 1; if (neighborrow >= 0 && neighborcolumn >= 0) { if( cells[neighborrow][neighborcolumn].traversable) { neighbors[4] = cells[neighborrow][neighborcolumn]; } } // bottom/right neighborcolumn = currentcolumn + 1; neighborrow = currentrow + 1; if (neighborrow < rows && neighborcolumn < cols) { if( cells[neighborrow][neighborcolumn].traversable) { neighbors[5] = cells[neighborrow][neighborcolumn]; } } // top/right neighborcolumn = currentcolumn + 1; neighborrow = currentrow - 1; if (neighborrow >= 0 && neighborcolumn < cols) { if( cells[neighborrow][neighborcolumn].traversable) { neighbors[6] = cells[neighborrow][neighborcolumn]; } } // bottom/left neighborcolumn = currentcolumn - 1; neighborrow = currentrow + 1; if (neighborrow < rows && neighborcolumn >= 0) { if( cells[neighborrow][neighborcolumn].traversable) { neighbors[7] = cells[neighborrow][neighborcolumn]; } } } return neighbors; } } astaralgorithm.java
import java.util.arraylist; import java.util.comparator; import java.util.hashset; import java.util.list; import java.util.priorityqueue; import java.util.set; /** * a* algorithm http://en.wikipedia.org/wiki/a*_search_algorithm */ public class astaralgorithm { public class cellcomparator implements comparator<cell> { @override public int compare(cell a, cell b) { return double.compare(a.f, b.f); } } /** * find cells can traverse given reference start point that's outside cell. * algorithm a* path finding, don't stop when found goal, neither consider calculation of distance. * @param g * @param start * @param goal * @param allowdiagonals * @return */ public set<cell> getfloodfillcells(grid g, cell start, boolean allowdiagonals) { cell current = null; set<cell> closedset = new hashset<>(); set<cell> openset = new hashset<cell>(); openset.add(start); while (!openset.isempty()) { current = openset.iterator().next(); openset.remove(current); closedset.add(current); (cell neighbor : g.getneighbors(current, allowdiagonals)) { if (neighbor == null) { continue; } if (closedset.contains(neighbor)) { continue; } openset.add(neighbor); } } return closedset; } /** * find path start goal. * @param g * @param start * @param goal * @param allowdiagonals * @return */ public list<cell> findpath( grid g, cell start, cell goal, boolean allowdiagonals) { cell current = null; boolean containsneighbor; int cellcount = g.rows * g.cols; set<cell> closedset = new hashset<>( cellcount); priorityqueue<cell> openset = new priorityqueue<cell>( cellcount, new cellcomparator()); openset.add( start); start.g = 0d; start.f = start.g + heuristiccostestimate(start, goal); while( !openset.isempty()) { current = openset.poll(); if( current == goal) { return reconstructpath( goal); } closedset.add( current); for( cell neighbor: g.getneighbors( current, allowdiagonals)) { if( neighbor == null) { continue; } if( closedset.contains( neighbor)) { continue; } double tentativescoreg = current.g + distbetween( current, neighbor); if( !(containsneighbor=openset.contains( neighbor)) || double.compare(tentativescoreg, neighbor.g) < 0) { neighbor.camefrom = current; neighbor.g = tentativescoreg; neighbor.h = heuristiccostestimate(neighbor, goal); neighbor.f = neighbor.g + neighbor.h; if( !containsneighbor) { openset.add( neighbor); } } } } return new arraylist<>(); } private list<cell> reconstructpath( cell current) { list<cell> totalpath = new arraylist<>(200); // arbitrary value, we'll have more 10 default java totalpath.add( current); while( (current = current.camefrom) != null) { totalpath.add( current); } return totalpath; } private double distbetween(cell current, cell neighbor) { return heuristiccostestimate( current, neighbor); // todo: dist_between heuristic_cost_estimate our use-case; use various other heuristics } private double heuristiccostestimate(cell from, cell to) { return math.sqrt((from.col-to.col)*(from.col-to.col) + (from.row - to.row)*(from.row-to.row)); } } the result inside cell logging is
inside: 2/2 inside: 7/3 inside: 8/3 inside: 8/4 inside: 2/6 inside: 3/6 inside: 4/6 the result path 0/0 8/8 is
[8/8, 7/7, 7/6, 6/5, 5/4, 5/3, 5/2, 4/1, 3/0, 2/0, 1/0, 0/0] i wrote editor in javafx, come blog post soon, if interested. grid this:
where
- black cells = walls
- green cells = traversable cells
- blue cells = path start end
- white cells = cells inside walls
the numbers ones a* algorithm:
- top/left = g (from start current cell)
- top/right = h (from current cell goal)
- center = f = g + h
and if don't allow diagonal movement:
but that's off-topic :-)
Comments
Post a Comment