fill algorithm
Author
hi!
where can I find infos/code about fill algorithms (like the fill functions in grahic programs)?
Or rather a algorithm that starts at a specific point in an 2d array and recognizes a closed area. I need that for a tile based RPG, which should only show the room in which the player is. (the rest is black). I want to try solving this problem with an algorithm on the fly.
bye
chris
there is the floodfill algorithm (good ol'' basic 
).
basically, start from a point (where the player is for example).
if point on the left is empty, mark it with a ''fill'' color and test its'' neighbours. If a neighbour is empty, mark it and test its neighbours, and so on, until you run out of points to mark. It''s a recursive algorithm BTW.
Note, for the flood fill, you don''t need the entire map, You can make a copy of the map from where the player stands, and to the area that the screen can see.
That algorithm is not very efficient, but should be fast enough really. Try it anyway. It does not require any pre-processing. You can make it faster by precomputing all the areas in the world, and looking at where the player stands, enable the areas marked at his position.
another approach would be to model the field of view of the actor, and mark cells that are inside that field of view, or around the player, making the ones on the edge of the field of view darker or blurrier.
Also, you can use this algorithm as a cheap A.I. path finding routine. Say you have a monster and you want it to go quickly towards the player. You floodfill the player position like above, and on each cells marked, instead of putting ''255'' in the cell, you put the distance from the cell to the player, that you increment by 1 on every recursions. That way, every cells marked will have the distance in cells from the player''s position. If you have a monster on the cell that has been filled, he will have a value stored in the cell telling him how far he is from the player. The surrounding cells will have different values. You just move the monster to the neighbouring cell that has the lowest value, and so on. They will converge towards the player. A bit like pacman.
you can improve the recursion by testing also the diagonal cells.
when you have a mosnter on a cell, the value on the cell would be, say 23, meaning he has to cross 23 cells minimum to get to the player. The cells around the cell ''23'' will either be 22, or higher than 23 (possibly all 24?). You pick a cell with a 22 (depending on the player''s relative position to the monster), and move the mosnter on that cell. Then you do the same the next frame. As the player moves, the values in the cells will change accordingly, but the monster will always have a choice of going to a cell which has the minimum ''cost''.
by adding extra parameters to the cells (like the slope, the altitude, the roughness of the terrain, if it provides cover, ect...), you can balance the cost from going to one cell to the next, and you chose the one with the minimum cost. Also, if the mosnter has a bow, and his at an optimum distance (say 5 cells separation), you can stop him, test for a clear line of sight, and make him fire an arrow at a safe distance. And you can use this algo for friendlies too, make them flee in panic (you inverse the cost), keep a safe distance, ect....
). basically, start from a point (where the player is for example).
if point on the left is empty, mark it with a ''fill'' color and test its'' neighbours. If a neighbour is empty, mark it and test its neighbours, and so on, until you run out of points to mark. It''s a recursive algorithm BTW.
int Fill (const 2DArray &Map, 2DCoord Start, 2DCoord *FilledPoints){ // make a copy of the map so we can stamp on it 2DArray MapCopy = Map; // clear the array of points ''seen'' by the player. int NumFilledPoints = 0; // recursively find the points that the player can ''see''. FillRecurse(MapCopy, Start, FilledPoints, NumFilledPoints); return NumFilledPoints;}void FillRecurse(2DArray &Map, 2DCoord Start, 2DCoord* FilledPoints, int& NumFilledPoints){ // store the value has being filled FilledPoints[NumFilledPoints++] = Start; // set the value at the filled coordinate to be != 0 Map.SetValue(Start, 255); // test point on the left 2DCoord Left(Start.x-1, Start.y); if (Left.x >= 0 && Map.GetValue(Left) == 0) { FillRecurse(Map, Left, FilledPoints, NumFilledPoints); } // test point on the right 2DCoord Right(Start.x+1, Start.y); if (Right.x < Map.Width && Map.GetValue(Right) == 0) { FillRecurse(Map, Right, FilledPoints, NumFilledPoints); } // test point above 2DCoord Top(Start.x, Start.y-1); if (Top.y >= 0 && Map.GetValue(Top) == 0) { FillRecurse(Map, Top, FilledPoints, NumFilledPoints); } // test point below 2DCoord Bottom(Start.x, Start.y+1); if (Bottom.y < Map.Height && Map.GetValue(Bottom) == 0) { FillRecurse(Map, Bottom, FilledPoints, NumFilledPoints); }} Note, for the flood fill, you don''t need the entire map, You can make a copy of the map from where the player stands, and to the area that the screen can see.
That algorithm is not very efficient, but should be fast enough really. Try it anyway. It does not require any pre-processing. You can make it faster by precomputing all the areas in the world, and looking at where the player stands, enable the areas marked at his position.
another approach would be to model the field of view of the actor, and mark cells that are inside that field of view, or around the player, making the ones on the edge of the field of view darker or blurrier.
Also, you can use this algorithm as a cheap A.I. path finding routine. Say you have a monster and you want it to go quickly towards the player. You floodfill the player position like above, and on each cells marked, instead of putting ''255'' in the cell, you put the distance from the cell to the player, that you increment by 1 on every recursions. That way, every cells marked will have the distance in cells from the player''s position. If you have a monster on the cell that has been filled, he will have a value stored in the cell telling him how far he is from the player. The surrounding cells will have different values. You just move the monster to the neighbouring cell that has the lowest value, and so on. They will converge towards the player. A bit like pacman.
#define CELL_WALL -1#define CELL_EMPTY 0void Fill (const 2DArray &OriginalMap, 2DCoord PlayerPos, const 2DArray &FilledMap){ // Prepare the filled map by clearing everything and putting up the walls of the map MapCopy.ClearFilledMap(FilledMap); // recursively find the cells that the player can ''see''. FillRecurse(FilledMap, Start, 1);}void FillRecurse(2DArray& Map, 2DCoord Pos, int NumberOfIterations){ // set the value of the cell as being the number of iterations Map.SetValue(Pos, NumberOfIterations); TestFill(Map, 2DCoord(Pos.x-1, Pos.y), NumberOfIterations); TestFill(Map, 2DCoord(Pos.x+1, Pos.y), NumberOfIterations); TestFill(Map, 2DCoord(Pos.x, Pos.y-1), NumberOfIterations); TestFill(Map, 2DCoord(Pos.x, Pos.y+1), NumberOfIterations); // diagonal cells TestFill(Map, 2DCoord(Pos.x-1, Pos.y-1), NumberOfIterations); TestFill(Map, 2DCoord(Pos.x+1, Pos.y-1), NumberOfIterations); TestFill(Map, 2DCoord(Pos.x-1, Pos.y+1), NumberOfIterations); TestFill(Map, 2DCoord(Pos.x+1, Pos.y+1), NumberOfIterations);}void TestFill(2DArray &Map, 2DCoord CellPos, int NumberOfIterations){ if (CellPos.x < 0 || CellPos.x > Map.Width || CellPos.y < 0 || CellPos.y > Map.Height) return; // the cell is empty, meaning we can fill it and carry on if (Map.GetValue(CellPos) == EMPTY_CELL) { FillRecurse(Map, CellPos, NumberOfIterations+1); } else { // if the value is an already filled value but is not a wall if (Map.GetValue(CellPos) != CELL_WALL) { // minimise the distance from player for that cell position if (Map.GetValue(CellPos) > NumberOfIterations) { Map.GetValue(CellPos) = NumberOfIterations; } } }} you can improve the recursion by testing also the diagonal cells.
when you have a mosnter on a cell, the value on the cell would be, say 23, meaning he has to cross 23 cells minimum to get to the player. The cells around the cell ''23'' will either be 22, or higher than 23 (possibly all 24?). You pick a cell with a 22 (depending on the player''s relative position to the monster), and move the mosnter on that cell. Then you do the same the next frame. As the player moves, the values in the cells will change accordingly, but the monster will always have a choice of going to a cell which has the minimum ''cost''.
by adding extra parameters to the cells (like the slope, the altitude, the roughness of the terrain, if it provides cover, ect...), you can balance the cost from going to one cell to the next, and you chose the one with the minimum cost. Also, if the mosnter has a bow, and his at an optimum distance (say 5 cells separation), you can stop him, test for a clear line of sight, and make him fire an arrow at a safe distance. And you can use this algo for friendlies too, make them flee in panic (you inverse the cost), keep a safe distance, ect....
There are quite a few websites that describe the standard algorithm for scan converting polygons. This basically is a flood fill for polygons, and is the algorithm used by graphics hardware to fill in pixels within a triangle. It is different from a 2D floodfill algorithm:
www.cc.gatech.edu/gvu/multimedia/nsfmmedia/graphics/elabor/polyscan/polyscan1.html
www.cs.utk.edu/~huangj/CS594F02/scan.ppt - a very nice presentation on the subject
Or, do a google search on "polygon scan conversion" for many, many links.
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
www.cc.gatech.edu/gvu/multimedia/nsfmmedia/graphics/elabor/polyscan/polyscan1.html
www.cs.utk.edu/~huangj/CS594F02/scan.ppt - a very nice presentation on the subject
Or, do a google search on "polygon scan conversion" for many, many links.
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
