Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Gentlefish]

Do you guys know a way to solve a connected components problem that isn't brute force? The brute force method looks like this. Basically, you loop over every single tile, skipping ones that have already been flood-filled and doing a depth-first search otherwise. The grid shown in that example is pretty small, but I'm working with a pseudo-rectangular hex grid of size 128x128. It creates a noticeable frame drop whenever I run it. Not too bad, but I want to improve it if possible.

The tiles are terrain types, all but one of them being land. The flood fill detects contiguous chunks of terrain tiles of the same type, but in addition to this I need to detect water and landmasses separately. A landmass can have many terrain type regions in it. Right now, I'm thinking of saving the coordinate of a single tile in each region, then after I detect all the regions I'll perform an A* pathfinding check between regions to tell if they're in the same landmass. Summing up the sizes of the regions gives me the landmass size.

Does it have to do with the differentiation of terrain types maybe? Are you checking for simply "water" and "not water" or "water", "plains", "forest", etc?

[miauw62]

I've just started the Euler problem archive. Now I have to relearn file I/O because I don't want to enter the gigantic number for Problem 8. 

This is why I like UVA. You just use cin and cout and the website does the rest.

[TheDarkStar]

I've just started the Euler problem archive. Now I have to relearn file I/O because I don't want to enter the gigantic number for Problem 8. 

This is why I like UVA. You just use cin and cout and the website does the rest.

I've finished that problem. I still don't think I really get how file I/O works, but I did learn that the characters 0-9 are not the same as the numbers 0-9. Also, several of the challenges are similar enough to copy half of the solution for another challenge.

[highmax28]

Stupid question, but is it possible to convert a javascript program into a screensaver? I added some things to that cloud loop and cleaned it up to make this awesome looking earthbound themed loop.

Here's the file as is if you want to look at it.

Spoiler (click to show/hide)

https://www.mediafire.com/?v4zxbiyv2wcn4qi

[Putnam]

I'm pretty sure screensavers are .exe files renamed to .scr

[Gatleos]

Could you maybe describe your problem in more detail? Why, when and how often are you doing a floodfill? I need more context please. Also maybe some source. After all, you could be doing something entirely different wrong.

In practice the flood-fill would happen rarely. Right now running it every frame makes the frame time go from ~16ms (60fps) to ~350ms. I'll try to get some pseudocode that explains it, for now I'll explain it a bit more.

The algorithm loops through every tile on the map one by one. If it finds a tile which hasn't already been seen, it performs a depth-first flood-fill out from that tile. All tiles examined by the flood-fill are marked as seen, so the main loop will skip over them. So most tiles get examined twice, once by the main loop and once by the flood-fill.

Part of the slowness may be due to needing to convert between axial and cartesian coordinates for the hex grid. Also, the tiles are stored in an unordered_map with their axial coordinate as the key value. They must be retrieved from there (after coordinate conversion) to view their type during the flood-fill.

Does it have to do with the differentiation of terrain types maybe? Are you checking for simply "water" and "not water" or "water", "plains", "forest", etc?

I'm attempting to get both. That is:

• All contiguous areas of water
• All contiguous areas of land (terrain type doesn't matter)
• All contiguous areas of the same terrain type

Landmasses commonly contain dozens of contiguous terrain regions.

[highmax28]

I'm pretty sure screensavers are .exe files renamed to .scr

I'm still new to this thing as I'm still learning. You'll have to forgive me for saying this, but is there a way to convert them into .exe files then?

[Putnam]

http://stackoverflow.com/questions/16584589/converting-html-javascript-to-an-exe

[Reelya]

I've just started the Euler problem archive. Now I have to relearn file I/O because I don't want to enter the gigantic number for Problem 8. 

Just cut and paste it as a string literal. you only have to remove the newlines.

[MagmaMcFry]

Also, the tiles are stored in an unordered_map with their axial coordinate as the key value. They must be retrieved from there (after coordinate conversion) to view their type during the flood-fill.

There you go, that's your problem. Use a 1d or 2d array, not an unordered_map. That will make your algorithm much faster. Also, as a minor optimization, coordinate conversion should run in constant time, and since it's time-critical and heavily used, make sure your coordinate conversion doesn't use any conditional statements such as ifs or ?:s.

[Gatleos]

Also, the tiles are stored in an unordered_map with their axial coordinate as the key value. They must be retrieved from there (after coordinate conversion) to view their type during the flood-fill.

There you go, that's your problem. Use a 1d or 2d array, not an unordered_map. That will make your algorithm much faster. Also, as a minor optimization, coordinate conversion should run in constant time, and since it's time-critical and heavily used, make sure your coordinate conversion doesn't use any conditional statements such as ifs or ?:s.

Yeah, I know it's slow compared to a linear array. The problem is that I need to store a square map, and that won't work with a hex grid stored in a linear array. See here. There is a ton of unused space unless I use a non-contiguous storage method. And tiles are easiest/fastest to look up in an associative container.

But if that's the problem, I guess there's nothing else I can do.

[MagmaMcFry]

Also, the tiles are stored in an unordered_map with their axial coordinate as the key value. They must be retrieved from there (after coordinate conversion) to view their type during the flood-fill.

There you go, that's your problem. Use a 1d or 2d array, not an unordered_map. That will make your algorithm much faster. Also, as a minor optimization, coordinate conversion should run in constant time, and since it's time-critical and heavily used, make sure your coordinate conversion doesn't use any conditional statements such as ifs or ?:s.

Yeah, I know it's slow compared to a linear array. The problem is that I need to store a square map, and that won't work with a hex grid stored in a linear array. See here. There is a ton of unused space unless I use a non-contiguous storage method.

Consider this: You have jiggabytes of available memory, but you're already short on runtime (for no evident reason). I think the tradeoff is worth it.

And tiles are easiest/fastest to look up in an associative container.

They're waaaay faster to look up by array index, it's literally a single machine instruction. Associative containers have tons of stuff going on in the background.

PS: I still think you're doing something entirely else wrong. Have you tried counting the number of calls to floodfill(...) per tick?

[Gatleos]

They're waaaay faster to look up by array index, it's literally a single machine instruction. Associative containers have tons of stuff going on in the background.

The fastest when it comes to non-contiguous structures like linked lists, I mean.

Consider this: You have jiggabytes of available memory, but you're already short on runtime (for no evident reason). I think the tradeoff is worth it.

Yep, that's probably the best option. It just feels so wrong

PS: I still think you're doing something entirely else wrong. Have you tried counting the number of calls to floodfill(...) per tick?

I counted the calls to floodFill(), and it's always the same as the number of regions found. It couldn't be less than that, and there are no redundant calls.



EDIT: goddammit, the frame time is significantly less than 350ms when running the function, I forgot to go back to release build. It's still a slowdown, just not as much as I said. I got some ideas to speed it up anyway, though.

[bahihs]

Alright guys, Stackoverflow failed me and I need some help with my libtcod+python Field of View code.

Basically there are several units (~10 on each team with 2 teams) and each one has its own sight range (~5-10). I need to create a set of all the tiles on the map which should be highlighted based on the total FOV of all units. I'm not playing with light intensity or any such shenanigans so I just need a simple on/off toggle of the tile.

Here's what I have:

Code: [Select]

class Unit:
    #This is a generic unit: cavalry, infantry etc.

    def __init__(self, name, x, y, char, color,
                 move_range, atk_range, unit_size, morale, base_power, base_defence,
                 fatigue, team):
        self.name = name
        self.x = x
        self.y = y
        self.char = char
        self.color = color

        self.range = move_range
        self.move_counter = 0
        self.atk_range = atk_range
        self.sight_range = 5
        self.fov_map = libtcod.map_new(self.sight_range, self.sight_range)
        self.visible_set = set([])

        self.exp = 0
        self.rank = ''
        self.rank_level = self.exp/10
       
        self.unit_size = unit_size
        self.current_unit_size = unit_size

        self.morale = self.exp + morale
        self.current_morale = morale
       
        self.fatigue = fatigue + self.exp
        self.current_fatigue = fatigue

        self.base_power = base_power + self.rank_level
        self.base_defence = base_defence + self.rank_level
        self.power_multiplier = 1
        self.power = self.power_multiplier*self.base_power
        self.defence = self.power_multiplier*self.base_defence

        self.team = team
        self.targeted = False
        self.can_move = False
        self.can_attack = False
        self.inactive_color = libtcod.gray

    def draw(self, screen):
        #set the color and then draw the character that represents this object at its position
        #if libtcod.map_is_in_fov(new_map, self.x, self.y):
        if game_ready == True:
            if self.can_move == True or self.can_attack == True:
                libtcod.console_set_default_foreground(screen, self.color)
            elif self.can_move == False and self.can_attack == False:
                libtcod.console_set_default_foreground(screen, self.inactive_color)
            #elif game_ready == False:
                #libtcod.console_set_default_foreground(screen, self.color)
        libtcod.console_put_char(screen, self.x, self.y, self.char, libtcod.BKGND_NONE)
        libtcod.map_set_properties(new_map, self.x, self.y, False, False)

    def set_fov(self): #Relevant function to the issue
       
        sight_range_tiles = get_tiles_in_range(self.x, self.y, self.sight_range) #Gets the coordinates of the tiles within a certain range (in this case, the sight range)
        self.visible_set = {tile for tile in T_Map.tile_array if (tile.x, tile.y) in sight_range_tiles} #Gets all the tiles with the corresponding coords in sight_range_tiles
 
        self.blocked_tiles_set = (self.visible_set & terrain_tiles_set) #Creates a subset of the visible tiles by intersecting with a different set, terrain_tiles_set, which contains all the tiles which block light; thus blocked_tiles_set contains all the tiles within range which block light
       
        #Iterates through light-blocking tiles in range and assigns them as blocked to a separate, unique FOV map for each unit
        for tile in self.blocked_tiles_set:
            libtcod.map_set_properties(self.fov_map, tile.x, tile.y, False, True)

        libtcod.map_compute_fov(self.fov_map, unit.x, unit.y, self.sight_range, True, libtcod.FOV_SHADOW)

def render_all():
    global color_dark_wall
    global color_dark_ground
    global lclick_x, lclick_y
    global coord_in_range
    global new_map
    global game_ready
    global fov_recompute
    global turn_counter
       
    #render map
    if map_archetype == 'forest':
        T_Map.render_map(T_Map.tileset_forest, T_Map.colors_forest, T_Map.terrain_forest)
    elif map_archetype == 'desert':
        T_Map.render_map(T_Map.tileset_desert, T_Map.colors_desert, T_Map.terrain_desert)
    elif map_archetype == 'tundra':
        T_Map.render_map(T_Map.tileset_tundra, T_Map.colors_tundra, T_Map.terrain_tundra)
    elif map_archetype == 'plains':
        T_Map.render_map(T_Map.tileset_plains, T_Map.colors_plains, T_Map.terrain_forest)
 
   
    #draw all objects in the list and compute the field of view
    for team in teams:
        for unit in team:
            if fov_recompute:
                if unit.team == 1:
                    unit.set_fov()
 
                elif unit.team == 2:
                    unit.set_fov()


            #Team 1
            if (turn_counter%2 == 0 or turn_counter == -1):
                for fov_map in fov_maps1:
                    if unit.team == 1 or libtcod.map_is_in_fov(fov_map, unit.x, unit.y):
                        unit.draw(con)

            #Team 2
            if turn_counter%2 == 1 or turn_counter == -1:
                for fov_map in fov_maps2:
                    if unit.team == 2 or libtcod.map_is_in_fov(fov_map, unit.x, unit.y):
                        unit.draw(con)
               
    #       
         
    visible_1 = []
    visible_2 = []
   
    #Change the color of a tile if it is in the FOV.
    for x in range(MAP_WIDTH):
        for y in range(MAP_HEIGHT):
            for unit in team1:
                visible_1 += [libtcod.map_is_in_fov(unit.fov_map, x, y)]
            for unit in team2:
                visible_2 += [libtcod.map_is_in_fov(unit.fov_map, x, y)]
            if turn_counter%2 == 0 and any(visible_1):
                libtcod.console_set_char_background(con, x, y, libtcod.darker_purple, libtcod.BKGND_SET)
            elif turn_counter%2 == 1 and any(visible_2):
                libtcod.console_set_char_background(con, x, y, libtcod.darker_purple, libtcod.BKGND_SET)
Not only does this code not display anything (as in no FOV for either side) it also lags like hell. The latter I expected (since I'm iterating through 5000 objects every time render_all() runs, which is looping until exit) but the former is giving me a headache. Help.

EDIT: Nevermind, it turns out it was a simple fix. This is what happens with sleep deprivation. Good to know.

[Reelya]

Also, the tiles are stored in an unordered_map with their axial coordinate as the key value. They must be retrieved from there (after coordinate conversion) to view their type during the flood-fill.

There you go, that's your problem. Use a 1d or 2d array, not an unordered_map. That will make your algorithm much faster. Also, as a minor optimization, coordinate conversion should run in constant time, and since it's time-critical and heavily used, make sure your coordinate conversion doesn't use any conditional statements such as ifs or ?:s.

Yeah, I know it's slow compared to a linear array. The problem is that I need to store a square map, and that won't work with a hex grid stored in a linear array. See here. There is a ton of unused space unless I use a non-contiguous storage method. And tiles are easiest/fastest to look up in an associative container.

But if that's the problem, I guess there's nothing else I can do.

There's definitely something you can do. You don't have to adhere to the coordinate system offered in your link. I do hex grids just by offsetting every odd line by a half unit. You need to tweak the function for adjacency, but it makes the storage and speed much better. After that you reference movement by directions, and that gets mapped to changes of cell coordinate based on whether it's an even or odd row.

Associative containers might be easier for the programmer, but they're a nightmare of overhead for your CPU. Definitely not something you want to use in a production app. Work out rules for accessing your fast data structure consistently, then wrap those rules up in a class or something so that they're easy to use. It's a little extra work, but it's a one-off and after that they're just as easy to use as any associative map, if not more so because they're customized.