Python Forum

Full Version: Efficient algorythm for checking occupied fields.
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
Hi, I'm making a game - something like this - my game changes in detaile, but for describing my problem, that game is great. I have a problem with marking a area.

Rules of the game (if you play in linked game for a minute, you will get if - it's basically described what pacman and ghosts do in that game):

On the map there is a player and enemies.When starting, whole map is empty (all fields are unoccupied).While player is moving through unoccupied area (the dark one on liked game) he is marking his path behind. If the enemy (ghost) hits the mark, player dies. This part is pretty easy - I a 2d array with numbers, where 0 = unoccupied area, 1= occupied and 2 = marked area, I just draw appropriate tiles and check array when objects are moving.
The problematic part comes, when player goes from unoccupied area to occupied area. There are three scenarios (this part is exactly the same as in linked game):
* the occupied tile is not connected with the edges of the map (this can happen when enemy destroys few tiles hitting them, and few are left alone in the middle of the map) - then marked path should be draw as occupied area,
* the player marks the path between two occupied areas, both connected to the map edges, then he makes two separated areas and two things can happen:
** first his path is marked as occupied,
** if on the first separated area is enemy (ghost) don't do anything,
** if on the first separated area there are no enemies, mark whole area as occupied,
** the same for second area

--- end of rules :)

As you see I described you something very similar as linked game, my will be different in details and is made mostly to learn python and have fun, but I have big problem with the last part, when I have to decide what to do if player goes from unoccupied to occupied area.
I could check tiles recursive - first the one I stand on, then her neighbours, then return true or false, but complexity of samthing like that is tragic (my map will have around 200 fieds).

Do you have some idea how to check and mark appropriate area, and don't have tons on computations at once?
(Apr-17-2019, 09:29 AM)kq2211 Wrote: [ -> ]I could check tiles recursive - first the one I stand on, then her neighbours, then return true or false, but complexity of samthing like that is tragic (my map will have around 200 fieds).
I think this is a valid approach. This is one of the few times i would say recursive is the right method for the job. I would crawl to every adjacent space until either there is an enemy in the space (flood the wrong section) and fail, there are no more spaces left with 0 claimed territory (you are in your territory) and fail, there are no more spaces left with at least 1 claimed territory (completed a territory) and success. All fails would result in no territory changes, while success would claim said territories for yourself.

Each block from the starting location would check its north, east, west, and south value. The starting location could be your guy just before he closes the section off. At this point you would have to determine that either side is two different sections to compare.

I did something similar in a replica game of flood it. It was about 200 fields, and i didnt have a problem with this method and it worked great. I would be careful of what you put in that recursive method though. Only compare and confirm changes. If you draw (or something else resource intensive) you can easily bottleneck your program down.
If you don't mind using NumPy and SciPy.
You could just avoid the algorithm.
import numpy as np
from scipy.ndimage import label

def main():
    board = np.random.randint(0, 2, size=(10, 10))
    area, count = label(board)
    locations = np.where(area == 4)

    print(board, '\n')
    print(count, '\n')
    print(area, '\n')
    print(locations)

main()
Here a quick floodit example using NumPy and SciPy.
import pygame
import numpy
from scipy.ndimage import label as sci_label

# Simple Scene Interface
class Scene:
    def draw(self, surface, game): pass
    def event(self, event, game): pass
    def update(self, game): pass

class Game:
    def __init__(self, caption, width, height):
        # Basic pygame setup
        pygame.display.set_caption(caption)
        self.rect = pygame.Rect(0, 0, width, height)
        self.surface = pygame.display.set_mode(self.rect.size)
        self.clock = pygame.time.Clock()
        self.running = False
        self.fps = 30
        self.delta = 0

        # Scene Interface
        self.scene = Scene()
        Game.info = self

    def mainloop(self):
        self.running = True
        while self.running:
            for event in pygame.event.get():
                self.scene.event(event, self)

            self.keys = pygame.key.get_pressed()

            self.scene.update(self)
            self.scene.draw(self.surface, self)
            pygame.display.flip()
            self.delta = self.clock.tick(self.fps)

class FloodIt(Scene):
    def __init__(self):
        self.colors = tuple(map(pygame.Color,
            ['dodgerblue', 'gold', 'firebrick1', 'darkslateblue',
             'forestgreen', 'darkorange', 'mediumorchid'] ))

        self.surface = pygame.Surface((420, 420))
        self.new_game()

    def new_game(self):
        self.grid = numpy.random.randint(1, 8, size=(14, 14)).astype(numpy.uint8)
        self.update_grid()

    def draw(self, surface, game):
        surface.blit(self.surface, (190, 100))

    def event(self, event, game):
        if event.type == pygame.MOUSEBUTTONDOWN:
            if event.button == 1:
                x, y = event.pos
                if 190 < x < 610:
                    if 100 < y < 520:
                        self.selected_block((x - 190) // 30, (y - 100) // 30)
        elif event.type == pygame.KEYDOWN:
            if event.key == pygame.K_SPACE:
                self.new_game()
        elif event.type == pygame.QUIT:
            game.running = False

    def selected_block(self, x, y):
        if self.grid[0, 0] != self.grid[x, y]:
            value = self.grid[x, y]
            v = self.grid[0, 0]
            vl, vc = sci_label(self.grid == v)
            # Assume first group will always be right
            w = numpy.where(vl == 1)
            for x ,y in zip(*w):
                self.grid[x, y] = value

            self.update_grid()

    def update_grid(self):
        for x, row in enumerate(self.grid):
            for y, col in enumerate(row):
                self.surface.fill(self.colors[col - 1], (x * 30, y * 30, 29, 29))

def main():
    pygame.init()
    game = Game("FloodIt", 800, 600)
    game.scene = FloodIt()
    game.mainloop()
    pygame.quit()

main()