Print

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

[Max White]

It sounds a lot like you want the foreach loop

Code: [Select]

Player[] players = Blah.MakePlayers(); //Or however you get this array you want to go through

foreach (Player p in players) //This starts a loop that will go through every element in an array
{
p.Position++;
}
If that doesn't fill your need, we might need to break out LINQ.
See that using statement at the top of your code for LINQ? That thing is cool, can do some awesome shit.

[Max White]

Switching from properly coded python to properly coded C++ rarely increases the speed by more than a factor 7, so things are still going to be slow.

If I were you, the first thing I would tackle is your drawing algorithm. First of all, you don't need to redraw tiles that don't change. Secondly, you should only draw tiles that the player can actually see and you're not going to see all of the 1.000x1.000 map at once. Finally, the major part of your levels isn't going to change. You can draw the whole level at once (or in chunks) and store that, then blit the level and blit any updates over it. Blitting a single image is fast as hell.

Already only drawing tiles on screen. Currently redrawing the entire console, but I can change that.

Thinking of just making a design choice and not updating the tiles every frame, so that unless an actor does something to make a change, the level remains the same.

If I really need a tile updated, I guess I could have the level store a delegate that the tiles could subscribe themselves to, because the vast majority of tiles don't even need to be updated anyway.

As I'm only drawing what is on screen, without updating each tile the size of the level should become a lot less significant.

Oh that's even less of a difference then, as you don't have to bother with an interpreter and memory allocation is blazing fast in the .net VM (At the 'cost' of having a garbage collector). Difference between C# and C++ is roughly a factor 2, depending on application of course. From his description, max was aiming for a speed increase of a factor 4000 or something and no language can give you that much of a speed increase.

A factor of two would be valuable, as everything I do to optimise current code would be increased by that factor of two...

[Levi]

If you like I can post my rendering/updating (with libtcod) strategy once I get home from work(because hell if I remember what I did).  It seems pretty efficient so far.

[Aqizzar]

It sounds a lot like you want the foreach loop

Code: [Select]

Player[] players = Blah.MakePlayers(); //Or however you get this array you want to go through

foreach (Player p in players) //This starts a loop that will go through every element in an array
{
p.Position++;
}

That actually isn't what I was looking for, but it's fascinating anyway.  There's all sorts of basic functions like foreach, and letter.Array stuff that I don't know.  MSDN's documentation on small-a arrays is pretty curt.

[Max White]

Well without updating the tiles I'm getting an extra 10fps... Although that is with a map of 1,000 by 1,000 as opposed to having before when it was one hundredth the size. I think c# might be able to handle this then, as 1,000 by 1,000 certainly does make for a vast battle field to explore!

Spoiler (click to show/hide)

I'm also going to work off the assumption that if you are planing with multiple people, who ever has the best computer will host, and they most likely have some more power under the hood than this little lap top.

[Levi]

Levi's libtcod rendering strategy:

Consoles:

- map_console  #As big as the entire map
- screen_console #as big as the screen

The map_console is an up-to-date snapshot of the entire map.  libtcod is pretty quick for modifying non-rendered consoles, so speed isn't a huge issue here.  The screen_console copies the relevant portions of the map_console to it every tick.  Copying(or blitting) a rectangle is also a very fast operation.   You can then add things like overlays, side panels, FPS meters or whatever onto the screen_console.  The final step is that the screen_console blits to the root console so that everything is actually displayed.

Now I only need to worry about having a completely updated map_console, because the blitting to the screen_console is trivial.  I don't want to check every single tile to see if it needs updating, because with a big map that would take forever.  So I keep a special list called my redraw_list.

variables
- redraw_list #array
- redraw_all  #boolean, normally false.
- monster_list #array of my monsters

So you can probably already see where I'm going with this.  In the main game loop, I'll have characters moving around, tiles being changed and other important things to draw.  So every time something changes, I add the tiles that would need to be redrawn to the redraw list.

For example:

Code: [Select]

#pseudocode
def walk_east(monster)
  redraw_list.push([monster.x, monster.y]) #add the current position to the redraw list
  monster.x += 1
  redraw_list.push([monster.x, monster.y]) #add the new position to the redraw list
end
So here we add the current position and the new position of a monster to the redraw_list.  Once every single player/monster/whatever has taken its turn we start the render function.

The render function just redraws each location in its list.  If redraw_all is true, it'll redraw the entire map(useful for when the game is starting up).

Code: [Select]

#pseudo_code
def default_render(map):
    if(redraw_all == True):
        tile = None
        for y in range(0, map.size - 1):
            for x in range(0, map.size - 1):
                draw_tile(map, x, y)
            end
        end
    else:
        for elem in redraw_list:
            draw_tile(map, elem[0], elem[1])
        end
    end
    redraw_list = []
    redraw_all = False
end
The only problem with this, is that often things like items or monsters are going to be in a list, and not quickly obtainable with an x, y value.  If I was redrawing location 100,53 then I would need to go through my entire monster list to see if any monsters were at those particular coordinates.  If I redrew 10 tiles in a turn, I'd have to go through that list about 10 times.  That is no good, so I decided to give monsters a redraw boolean.

So my walk_east would change to:

Code: [Select]

#pseudocode
def walk_east(monster)
  redraw_list.push([monster.x, monster.y]) #add the current position to the redraw list
  monster.x += 1
  monster.redraw = True
end
and my rendering would look like:

Code: [Select]

#pseudo_code
def default_render(map):
    if(redraw_all == True):
        for y in range(0, map.size - 1):
            for x in range(0, map.size - 1):
                draw_tile(map, x, y)
            end
        end
    else:
        for elem in redraw_list:
            draw_tile(map, elem[0], elem[1])
        end
    end
    for mon in monster_list:
        if mon.redraw or redraw_all or [mon.x, mon.y] in redraw_list:
            draw_monster(mon)
            mon.redraw = False
        end
    end
 
    redraw_list = []
    redraw_all = False
end
This still isn't quite perfect, as we are still having to loop through the redraw list for many of the monsters.  I might need to improve that later, but for now its giving me pretty good efficiency.  Probably an even better method would be to create some kind of hash map that takes coordinates as a key and has an array of "monsters/items that are here".  This would give even better speeds as all lookups wouldn't need any loops.  The downside is that I'd need to be very careful about keeping the hash map accurate.

I'll think on that hash map thing a bit more, sounds like it could be useful.

[Mego]

Hashmaps/dictionaries are great. I'm having to re-write a bunch of code written by someone who doesn't know what a hashmap is. It's exactly as bad as it sounds.

[Aqizzar]

...I don't know what hashmaps and dictionaries are.  So uh, what are they?  And what makes them so great?

[RulerOfNothing]

A hash map or dictionary is, as I understand it anyway, a means of implementing associative arrays which allow you to address a list of items by some arbitary type (such as a character string).

[Max White]

...I don't know what hashmaps and dictionaries are.  So uh, what are they?  And what makes them so great?

You know how Dave held items? It's like that.

[Mego]

Only less Scrabble-y and more useful. And it doesn't have to be strings for key values.

[kaenneth]

...I don't know what hashmaps and dictionaries are.  So uh, what are they?  And what makes them so great?

Fast lookups in large lists of objets.

First you have to know what a binary search is, it's like how you (should) search a phone book, or a real life paper dictionary, start in the middle, and keep splitting in half until you find the item.

A dictionary (IIRC, I might be wrong, a dictionary could use a hashtable internally to store it's keys) does this on the field you specify as the key; so that a thousand item dictionary can be searched in 10 tests, or a million items searched in 20.

Then you have to know what a Hash is, it's a number generated from an object; a simple example of a hash would be to take the sum of the digits of a phone number, and then only keeping the last digit, so 555-1212 sums to 21, so a hash could be '1'.

A hashmap allows you to quickly locate a known object; it won't help you at all if you only have part of the data, like knowing the number ends with -1212 is useless in this case.

So, we have the phone number than hashes to '1', so we can store the '555-1212' in a sub-list (known as a bucket) referred to as '1'.

So, if we want to answer the question "Is 555-1212 on the do-not-call list?" we don't have to check bucket 0,2,3,4,5,6,7,8, or 9, only bucket 1; dividing the time to answer that type of question by the number of buckets (10)

A bucket can contain multiple items, '555-1221 -1122 -2211 -2112... all have the same sum of digits, so would end up within the same bucket; some hashtables (like the one in .net) automatically expand the table size as it gets fuller, trying to keep a balance between number of buckets, and the size of the buckets (as close to 1 as possible)

An advantage of a properly written and used Hashtable is that the entries are balanced, with an equal chance for any hash value; while if you load up a dictionary with phone numbers all in the same area code and prefix, it might waste time trying to narrow down to the whole set... like

500-000-0000
750-000-0000
625-000-0000
562-500-0000
...

which would be a watse if all your entries start with 555-XXX-XXXX

[Levi]

...I don't know what hashmaps and dictionaries are.  So uh, what are they?  And what makes them so great?

Edit:  Ninja'd.   Well I'm leaving my example anyway.   

The cool thing about hashmaps is that they have almost instant lookups. 

Lets say you have an array of 60 thousand monsters with names, and you need to check something on the monster "Harold".

With an array, you'd do something like:

Code: [Select]

mymonster = nil
for mon in monsters:
  if(mon.name == "Harold")
     mymonster = mon
     break
   end
end

So if Harold is at the end of the array, you'd have to iterate through that loop 60 thousand times.  That is no good, so we need a faster method.

A hash map lets you look up something on a unique key.  A good key in this case might be the name of the monster.

Code: [Select]

mon = monster_name_hash["harold"]

Easy as that!  You need to have filled in the hash map ahead of time, but that fine.  You only need to do that once.


You can even put arrays as the returning value if you need to keep a list of guys named harold.  Its pretty convenient once you get to know them.

[Aqizzar]

So I guess my real question is, do hashmaps and dictionaries exist as defined things in themselves in a programming language?  Or is it just a recognized construction, like an Object or Linked List, that has to be inferred through your coding methodology?

Because I do feel like I have a use for these pointers, I just don't know how to implement them.

[Mego]

I'm not sure how C# does hashmaps/dicts, but in C++, it's std::map, and in Python, it's like this:

Code: [Select]

mydict = {'hello' : 'world'}
mydict['goodbye'] = 'goodnight'
print mydict['goodbye'], mydict['hello'] # Output: goodnight world