SHARE
TWEET

floodfill works (can probably crash it though)

a guest Dec 20th, 2019 4 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // (c) authors of openttd, gpl, etc etc
  2. //
  3.  
  4. // this code is the bare minimum implementation for a flood-fill,
  5. // not including the additional enums and specification for adding the trigger button
  6. // or other configuration to the UI
  7.  
  8. #define USE_FLOODFILL 1
  9. #if USE_FLOODFILL
  10. // BEGIN FLOODFILL AMENDMENT
  11. #include <vector>
  12.  
  13. struct point_t
  14. {
  15.     point_t() {}
  16.     point_t(int _x, int _y) : x(_x), y(_y) {}
  17.     void operator=(point_t &p)
  18.     {
  19.         x = p.x;
  20.         y = p.y;
  21.     }
  22.     int x;
  23.     int y;
  24. };
  25.  
  26. template <typename T>
  27. struct floodfill_stack_t
  28. {
  29.     floodfill_stack_t()
  30.     {
  31.         stack.reserve(16);
  32.         stack.resize(16);
  33.         stack_pointer = 0;
  34.         max_stack = 0;
  35.     }
  36.     bool push(T t)
  37.     {
  38.         if (stack_pointer == stack.size() - 1) {
  39.             stack.reserve(stack.size() + 16);
  40.             stack.resize(stack.size() + 16);
  41.         }
  42.         stack[stack_pointer] = t;
  43.         stack_pointer++;
  44.         if (stack_pointer > max_stack) {
  45.             max_stack = stack_pointer;
  46.         }
  47.         return 1;
  48.     }    
  49.     bool pop(T &t)
  50.     {
  51.         if (stack_pointer > 0) {
  52.             t = stack[stack_pointer - 1];
  53.             stack_pointer--;
  54.             return 1;
  55.         } else {
  56.             return 0;
  57.         }    
  58.     }    
  59.     void clear()
  60.     {
  61.         stack_pointer = 0;
  62.     }
  63.     // index to last entry + 1
  64.     int stack_pointer;
  65.     // record of largest used stack size
  66.     int max_stack;
  67.     std::vector<T> stack;
  68. };
  69.  
  70. // apply change to selected tile
  71. using ffcb_apply_t = void(*)(TileIndex ti, const void *config_ptr, void *state_ptr);
  72. // return selected tile == target
  73. using ffcb_match_t = bool(*)(TileIndex ti, const void *target_ptr, const void *config_ptr, const void *state_ptr);
  74.  
  75. void floodfill(TileIndex t, ffcb_match_t match, ffcb_apply_t apply,
  76.     const void *config, const void *target, void *state)
  77. {
  78.     using BT = std::uintmax_t;
  79.     using T = point_t;
  80.     floodfill_stack_t<T> stack;
  81.     point_t p(TileX(t), TileY(t));
  82.  
  83.     const int width = MapSizeX();
  84.     const int height = MapSizeY();
  85.     const int x_min = 1;
  86.     const int x_max = width - 1;
  87.     const int y_min = 1;
  88.     const int y_max = height - 1;
  89.  
  90.     stack.clear();
  91.  
  92.     if (!stack.push(p)) {
  93.         return;
  94.     }
  95.        
  96.     while (stack.pop(p)) {    
  97.         int y1 = p.y;
  98.         while (y1 >= y_min) {
  99.             const TileIndex cursor = TileXY(p.x, y1);
  100.             const bool mark = match(cursor, target, config, state);
  101.             if (!mark) {
  102.                 break;
  103.             }
  104.             y1--;
  105.         }
  106.         y1++;
  107.                
  108.         bool span_left = false;
  109.         bool span_right = false;
  110.  
  111.         while (y1 < y_max) {
  112.             const TileIndex cursor = TileXY(p.x, y1);
  113.             const bool mark = match(cursor, target, config, state);
  114.             if (!mark) {
  115.                 break;
  116.             }
  117.  
  118.             // target match, write the new data
  119.             apply(cursor, config, state);
  120.             // ensure the modified data no longer matches the target!
  121.             //assert(match(cursor, target, config, state) == false);
  122.             if (match(cursor, target, config, state)) {
  123.                 __debugbreak();
  124.                 // (escape infinite loop)
  125.                 return;
  126.             }
  127.  
  128.             if (!span_left && p.x > x_min && match(TileXY(p.x - 1, y1), target, config, state)) {
  129.                     if (!stack.push(point_t(p.x - 1, y1))) {
  130.                         return;
  131.                     }
  132.                     span_left = true;
  133.             } else if (span_left && p.x > x_min && !match(TileXY(p.x - 1, y1), target, config, state)) {
  134.                     span_left = false;
  135.             }
  136.          
  137.             if (!span_right && p.x < x_max && match(TileXY(p.x + 1, y1), target, config, state)) {
  138.                     if (!stack.push(point_t(p.x + 1, y1))) {
  139.                         return;
  140.                     }
  141.                     span_right = true;
  142.             } else if (span_right && p.x < x_max && !match(TileXY(p.x + 1, y1), target, config, state)) {
  143.                     span_right = false;
  144.             }
  145.             y1++;
  146.         }
  147.     }
  148. }
  149.  
  150. struct ffcb_apply_river_config_t
  151. {
  152.     int height;
  153.     const void *target;
  154. };
  155.  
  156. void ffcb_apply_river(TileIndex tile, const void *config_ptr, void *state_ptr)
  157. {
  158.     DoCommand(tile, 0, 0, DC_EXEC | DC_AUTO | DC_FORCE_CLEAR_TILE, CMD_LANDSCAPE_CLEAR);
  159.     MakeRiver(tile, Random());
  160.     TileIndex tile2 = tile;
  161.     CircularTileSearch(&tile2, RIVER_OFFSET_DESERT_DISTANCE, RiverModifyDesertZone, nullptr);
  162.     MarkTileDirtyByTile(tile);
  163.     MarkCanalsAndRiversAroundDirty(tile);
  164.     CheckForDockingTile(tile);
  165. }
  166.  
  167. struct ffcb_match_flat_height_target_t
  168. {
  169.     int height;
  170. };
  171.  
  172. bool ffcb_match_flat_height(TileIndex tile, const void *target_ptr, const void *config_ptr, const void *state_ptr)
  173. {
  174.     if (GetTileSlope(tile) != SLOPE_FLAT) {
  175.         return false;
  176.     }
  177.     assert(target_ptr != nullptr);
  178.     const ffcb_match_flat_height_target_t &target =
  179.         *(ffcb_match_flat_height_target_t *)target_ptr;
  180.     return target.height == TileHeight(tile) && !IsWaterTile(tile);
  181. }
  182.  
  183. /**
  184.  * Floodfill from selected tile
  185.  * @param tile target tile
  186.  * @param flags type of operation
  187.  * @param p1 unused
  188.  * @param p2 unused
  189.  * @param text unused
  190.  * @return the cost of this operation or an error
  191.  */
  192. CommandCost CmdFloodFill(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32 p2, const char *text)
  193. {
  194.     WaterClass wc = Extract<WaterClass, 0, 2>(p2);
  195.  
  196.     /* Only the editor can execute a floodfill */
  197.     if (_game_mode != GM_EDITOR) return CMD_ERROR;
  198.  
  199.     //CommandCost cost(EXPENSES_CONSTRUCTION);
  200.     //CommandCost ret;
  201.  
  202.     if (GetTileSlope(tile) != SLOPE_FLAT) {
  203.         return_cmd_error(STR_ERROR_FLAT_LAND_REQUIRED);
  204.     }
  205.  
  206.     /* can't make water of water! */
  207.     bool is_water = IsTileType(tile, MP_WATER) && (!IsTileOwner(tile, OWNER_WATER) || wc == WATER_CLASS_SEA);
  208.     bool is_water_water = IsWaterTile(tile);
  209.  
  210.     if (flags & DC_EXEC) {
  211.         ffcb_match_flat_height_target_t target;
  212.         target.height = TileHeight(tile);
  213.         ffcb_apply_river_config_t config;
  214.         config.height = TileHeight(tile);// + fill height;
  215.         config.target = &target;
  216.         floodfill(tile, &ffcb_match_flat_height, &ffcb_apply_river, &config, &target, nullptr);
  217.     }
  218.  
  219.     //cost.AddCost(_price[PR_BUILD_CANAL]);
  220.  
  221.     CommandCost cost;
  222.     cost.AddCost(0);
  223.     //return_cmd_error(STR_ERROR_ALREADY_BUILT);
  224.     return cost;
  225. }
  226. // END FLOODFILL AMENDMENT
  227. #endif
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top