- Generated by
1.9.1
|
penguins
1.0.0
|
Go to the source code of this file.
Data Structures | |
| struct | BotFloodFillCtx |
| See bot_flood_fill_count_fish. More... | |
Macros | |
| #define | bot_alloc_buf(buf, capacity, size) ((size_t)1 * size > capacity ? (buf = realloc(buf, sizeof(*buf) * size), capacity = size) : 0) |
| A helper for allocating the buffers cached within the BotState. More... | |
| #define | stack_push(x1, x2, y, dy) flood_fill_push(&stack, &stack_len, &stack_cap, x1, x2, y, dy, alloc_stack, data) |
Functions | |
| void | init_bot_parameters (BotParameters *self) |
| Initializes all fields of the given BotParameters to default values. More... | |
| BotState * | bot_state_new (const BotParameters *params, Game *game, Rng *rng) |
| Constructs a BotState (similarly game_new). More... | |
| void | bot_state_free (BotState *self) |
| Recursively destroys a BotState and its substates (similarly to game_free). More... | |
| BotState * | bot_enter_substate (BotState *self) |
| Allocates BotState::substate if necessary and returns it. More... | |
| static int | distance (Coords start, Coords end) |
| static int | pick_best_score (int scores_length, int *scores) |
| bool | bot_compute_placement (BotState *self, Coords *out_target) |
| Computes the best placement for the current player given the current game state. More... | |
| int | bot_rate_placement (BotState *self, Coords penguin) |
| Assigns a score to the placement at the given coordinates. More... | |
| bool | bot_compute_move (BotState *self, Coords *out_penguin, Coords *out_target) |
| Computes the best move for the current player given the current game state. More... | |
| BotMove * | bot_generate_all_moves_list (BotState *self, int penguins_count, Coords *penguins, int *moves_count) |
Creates a list with all the possible moves (as penguin -> target pairs) of the provided penguins. More... | |
| int * | bot_rate_moves_list (BotState *self, int moves_count, BotMove *moves_list) |
| Applies bot_rate_move to every move in the provided list and returns a pointer to the list of scores. More... | |
| int | bot_rate_move (BotState *self, BotMove move) |
| The heart of the bot, assigns a score to the given move according to its usefulness. More... | |
| bool | bot_quick_junction_check (BotState *self, Coords coords) |
| A precondition for junction checks to know if a more expensive flood fill test is necessary. More... | |
| short * | bot_flood_fill_reset_grid (BotState *self, short **fill_grid, size_t *fill_grid_cap) |
| Allocates a grid for use in bot_flood_fill_count_fish and fills it with zeroes. More... | |
| static bool | bot_flood_fill_check (int x, int y, void *data) |
| See bot_flood_fill_count_fish and flood_fill. More... | |
| static void | bot_flood_fill_mark (int x, int y, void *data) |
| See bot_flood_fill_count_fish and flood_fill. More... | |
| static FillSpan * | bot_flood_fill_alloc_stack (size_t capacity, void *data) |
| See bot_flood_fill_count_fish and flood_fill. More... | |
| int | bot_flood_fill_count_fish (BotState *self, short *grid, Coords start, short marker_value) |
| Counts all fish accessible within an enclosed area starting at the given point using the flood fill algorithm. More... | |
| static void | flood_fill_push (FillSpan **stack, size_t *stack_len, size_t *stack_cap, int x1, int x2, int y, int dy, FillSpan *(*alloc_stack)(size_t capacity, void *data), void *data) |
| void | flood_fill (int x, int y, bool(*check)(int x, int y, void *data), void(*mark)(int x, int y, void *data), FillSpan *(*alloc_stack)(size_t capacity, void *data), void *data) |
| An implementation of flood fill using the span filling algorithm. More... | |
| #define bot_alloc_buf | ( | buf, | |
| capacity, | |||
| size | |||
| ) | ((size_t)1 * size > capacity ? (buf = realloc(buf, sizeof(*buf) * size), capacity = size) : 0) |
A helper for allocating the buffers cached within the BotState.
Checks if the buffer has enough capacity for data of the requested size, if not – reallocates it at the requested size. The capacity and size arguments are the number of elements (not the number of bytes), and are implicitly converted to size_t (the multiplication by 1 is used for that).
| #define stack_push | ( | x1, | |
| x2, | |||
| y, | |||
| dy | |||
| ) | flood_fill_push(&stack, &stack_len, &stack_cap, x1, x2, y, dy, alloc_stack, data) |
| void init_bot_parameters | ( | BotParameters * | self | ) |
Initializes all fields of the given BotParameters to default values.
Definition at line 31 of file bot.c.
Referenced by GamePanel::GamePanel().
| BotState * bot_state_new | ( | const BotParameters * | params, |
| Game * | game, | ||
| Rng * | rng | ||
| ) |
Constructs a BotState (similarly game_new).
Definition at line 42 of file bot.c.
Referenced by BotThread::BotThread().
| void bot_state_free | ( | BotState * | self | ) |
Allocates BotState::substate if necessary and returns it.
The only distance function that is relevant for us since penguins can move only along the axes.
Definition at line 114 of file bot.c.
Referenced by BotState::bot_rate_move(), and BotState::bot_rate_placement().
|
static |
Definition at line 118 of file bot.c.
Referenced by BotState::bot_compute_move(), BotState::bot_compute_placement(), and BotState::bot_rate_move().
Computes the best placement for the current player given the current game state.
The algorithm for the placement phase is very simple:
true if the function managed to find a placement, false if there are no possible placements for the player or if the computation was cancelled. The coordinates of the resulting tile are written to out_target. Definition at line 143 of file bot.c.
Referenced by BotPlacementThread::Entry().
Computes the best move for the current player given the current game state.
The overall algorithm is roughly the following:
Note that when evaluating moves recursively, the provided Game is modified instead of creating a copy of it each time. However, recursive evaluation currently has a significant limitation – it only considers sequences of moves of a single penguin, and doesn't take the opponents' moves into account at all (doing otherwise consumes too much computing time).
true if a move was found, false if there were no moves available for the player or if the computation was cancelled. If found, the move is written to out_penguin and out_target.The aggressive strategy proved to be very effective against other bots, which are usually passive (meaning that they simply try to collect fish) - it first blocks all other players and then collects the rest of the fish. It is even somewhat effective against humans because its aggressiveness essentially relies on the opponent making a mistake, which is not an unreasonable assumption when playing against a human (especially myself). Although, consequently, the stupidest bots, which are simply making literally the first available move after scanning the board (this is what the BOT_MOVEMENT_FIRST_POSSIBLE strategy does), ended up being the algorithm's fatal weakness (well, not exactly fatal, it can still win against those) – primarily because they are very persistent at just moving in a single direction.
Definition at line 295 of file bot.c.
Referenced by BotMovementThread::Entry().
Applies bot_rate_move to every move in the provided list and returns a pointer to the list of scores.
The heart of the bot, assigns a score to the given move according to its usefulness.
In case a cancellation is requested (see BotState::cancelled), this function starts unwinding the recursive calls and returns some garbage score, but otherwise the move computation is stopped.
A precondition for junction checks to know if a more expensive flood fill test is necessary.
A "junction" is a state when then bot has to choose between two or more directions because once it makes a move the other paths will become inaccessible. This function only performs a quick heuristic check which can only tell if the current tile is definitely not a junction, so it is used to know if a further more time-consuming flood fill test is necessary.
| short * bot_flood_fill_reset_grid | ( | BotState * | self, |
| short ** | fill_grid, | ||
| size_t * | fill_grid_cap | ||
| ) |
Allocates a grid for use in bot_flood_fill_count_fish and fills it with zeroes.
|
static |
See bot_flood_fill_count_fish and flood_fill.
|
static |
See bot_flood_fill_count_fish and flood_fill.
|
static |
See bot_flood_fill_count_fish and flood_fill.
Counts all fish accessible within an enclosed area starting at the given point using the flood fill algorithm.
Returns the number of reachable fish, the counted tiles are marked on the provided fill grid with marker_value, which must be non-zero. Additionally is used for junction checks.
| void flood_fill | ( | int | x, |
| int | y, | ||
| bool(*)(int x, int y, void *data) | check, | ||
| void(*)(int x, int y, void *data) | mark, | ||
| FillSpan *(*)(size_t capacity, void *data) | alloc_stack, | ||
| void * | data | ||
| ) |
An implementation of flood fill using the span filling algorithm.
This is essentially the algorithm behind the "bucket" tool in paint programs. The code was pretty much copied (and translated from pseudocode) from Wikipedia.
| x | the starting point |
| y | the starting point |
| check | a function that returns true if the given cell should be marked |
| mark | a function that marks the given cell |
| alloc_stack | a function that allocates that stack for FillSpan s |
| data | extra data to be passed into the provided functions |
Definition at line 725 of file bot.c.
Referenced by BotState::bot_flood_fill_count_fish().
1.9.1