willraman-blog

[willraman-blog]

It's been awhile since I posted. I hope you all are doing well.

If anyone is curious if I fell off the world or vaporwared, not yet. I adapted and pushed sideways into C#.

Oh and I found a programming job! With this new job I transitioned into a C# development position. Started out as a Software Analyst creating wireframes and visio documentation and saw an opening for programming and applied.

I am working on the next iteration of my game design hobby. C#, XNA 4.0 refresh and only a fraction of the effort it took in C++ I made this.

[willraman-blog]

I finished character selection today. Here are some shots.

The server sends authorized playable characters to the client, the client then loads the resources from the shared Sqlite3 db file and tileset. TCODlib renders the result.

Might be another week before I post the server application as freeware. Want to at least have it generate a world and let players run around on it and talk.

[willraman-blog]

Snapshots

I found a highly effective way of taking automatic snapshots. I used Gadwin printscreen, and an AutoIT script I wrote. Gadwin was configured to dump screenshots in a snaps directory and not prompt.

AutoIT script. alt-esc toggles pause, and shift-esc turns off the script.

Global $UnPaused HotKeySet("!{ESC}", "TogglePause") HotKeySet("+{ESC}", "Terminate") While 1 Sleep(100) WEnd Func TogglePause() $UnPaused = NOT $UnPaused if($UnPaused) then ToolTip("Capture on.",0,0) else ToolTip("Capture paused.",0,0) EndIf While $UnPaused Send("{PRINTSCREEN}") Sleep(5000) WEnd EndFunc Func Terminate() Exit 0 EndFunc

[willraman-blog]

Had an hour an a half to code today and put in Sqlite3 data read for entities and an ini file reader. Enjoy the movie.

I love to code.

[willraman-blog]

I've posted the client part of the legacy of a warlord multiplayer game on bitbucket. https://bitbucket.org/willraman/legacy-of-a-warlord-client

It is still pretty rough around the edges but it is shaping up nicely.

Soon as the client can connect with the server in a more robust fashion (character creation finished). I'll post the server application to http://www.legacyofawarlord.com.

Will

[willraman-blog]

I posted my new PHP budgeting app. Has a long way to go but it is a good start. Already immensely useful for me.

[willraman-blog]

A name and todo for version 1

I figured I will call this Quick and Easy budget (PHP). The license I decided on will be AGPL .

I added some date controls and am now trusting my budget to it. I'm not going to give something away unless I dogfood it. :)

Todo list for version 1.0, maybe one more week. major: 1. Database manager tab

 Add/remove tags (default seems to cover everything, but maybe it is too much or not enough?)

 Database cleaning(vacuum), dropping tables (ajax via PHP auto creates any missing table), direct downloading database for backup.

 Specify database location.

 Import CSV file to payments table. File format(duedate,info,tag,budget,amount)

 Import XML file to payments table. File format(<xml><row><duedate>data</duedate><info>data</info>...</row><row>...</row></xml>)

2. Line chart graph - Showing 3 plots, actual amount, budget amount and income. Maybe even a volume graph. Expenses fills up a volume of the income display. Not sure yet. 3. 3d pie chart for income vs. expense button added to current chart control.

4. Arrow moves view in month range (instead of just one month). If a difference in months is detected that is greater than 1. Every next arrow or previous arrow click increases months by that amount. This should give me the speed of navigation I want. 5. A spreadsheet report dump for tags and amount for the time period specified. Also an optional dump to PDF. I found a nice open source PDF exporter.

And a few minor fixes and code cleanup.

Version 0.9.1:

[willraman-blog]

About a week ago I looked at my billing/budgeting spreadsheet and it is completely overwhelming and unorganized.

I decided I need to better my web programming and database skills so I created a simple budgeting web page tool. It runs on PHP, ajax, and CSS3. The database is SQLite3. This is actually a perfect database for such a small app.

Here is a picture of version 0.9. When I finish this I will post 2 versions. A full application with apache/PHP engine zipped up. Also the PHP code by itself.

Probably licensed on LGPL.

[willraman-blog]

A new language to learn

Now this is interesting. If google continues to dominate the market, this might be the next language I decide to learn.

Dart - http://www.dartlang.org/

Language spec - http://www.dartlang.org/docs/spec/dartLangSpec.pdf

I think i'll give it a shot. I've been playing with PHP lately and writing a simple web game text hack for the legacyofawarlord.com site. I'll try this dart thing for the client side communications using dart.

[willraman-blog]

Popularity of Programming language

Found this in my wanders on the internet.

http://langpop.com/ http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html

Looks like C and C++ will be around a long time.

[willraman-blog]

A game update

A couple nights ago I got the UDP server working. I took the code from another project I worked on (encrypted UDP client/server), broke apart all the modules that made up legacy of a warlord, finally took the code from the tile memory manager project and squished them all together into 2 parts server/client.

The server currently handles:

Client session management

Packet encryption between client/server

Processing client event requests (after determining if it is valid) 

Multiple threads: client session manager and network thread (non-blocking UDP)

The client handles:

Display of tiles

User input

Sending event requests to the server (very simple commands like, <request move left>)

Processing packets based on server encryption key.

Moving forward now by adding in more modules from legacy of a warlord for the server. Next is the XML files for entities (mobs.xml). I decided I will split this file in half. Tiles/Ascii displayed will be controlled by the client. All the AI/attributes will be stored in the server.

I hope to have a release of the client up by Christmas and a server running somewhere on the internet. I think this time I will also try to have a linux release of the client. I really respect that community and like that OS.

[willraman-blog]

I use Mercurial

I've used subversion and tortoise SVN (as the client) to control my source code. I find it absolutely necessary when I break something to be able to diff my code and figure out what was the wrong path.

When LIBTCOD maintainers changed to mercurial I decided to do the same. I am very well pleased with the change myself. It was easy enough to import my SVN into the mercurial server and Tortoise HG makes it a snap to compare, merge and diff versions.

[willraman-blog]

Favorite STL container types c++

In the past week of coding/testing/profiling. I touched a few of the different STL container types.

Here is what I think about them:

1. STD::Vector. My favorite. Much like a standard c array, yet with a lot of methods attached to it. It is very quick. The ability to reserve space makes it absolutely effective in reducing memory bloat also saves me from having to manage the malloc/calloc/free.

2. STD::TR1::Unordered_Map. I use this on the HashNodesClass (branch object) storage, with only 40k - 100k keys it does a great job and is pretty fast. Seems to do a pretty good job managing it's memory bloat and is pretty quick on lookups. I originally tried to use this as containers for tiles but wasn't fast enough and the bloat was almost as bad as a std::map.

3. STD::Queue. I was playing with the idea of adding a cache method inside of the HashNodesClass class. Yet after a day of programming and testing, I found just using the random access method HashNodesClass::get was still quicker then going through the caching logic (even compared to a best case scenario of 100% cache hit rate on sequential reads). The checking of Queue.empty(), Queue.pop() and destructor of a std::pair<bool, unsigned int> all added up to 2 seconds for 20 million calls. Queue is pretty nice for its FIFO. I think if I were to play with caching again, I would try a STD::DeQueue (double ended queue).

4. Std::Map. For it's ease of use and automatic clean up,indexing, sorting, it is the dull swiss army knife of C++ type storage. It's great for anything that doesn't require a LOT of data in it and require fast lookups. I learned a useful tidbit to avoid. Nested maps are insanely slow on deconstruction.

In closing, of the C++ STL types, the vector speed wins (if you can effectively access the index). Map is easier to manage. Unordered_map(hash_map) seems to fall squarely in the middle. Every tool has its purpose and I now have a slightly better understanding of them.

[willraman-blog]

Previous posts picture. Full size. An OpenGL raw pixel display visual of my new c++ sparse data storage class.

[willraman-blog]

Finally, testing complete

I'm pretty satisfied with the results. I'm ready to move forward now that my sparse tile storage class is complete. I even took a few days to have some fun programming OpenGL on SDL. Attached is a picture of the pixel dump into a texture then displayed via a call to glTexSubImage2d.  

As you can see there is no visual loss of data from the original picture. This is a visual representation of the data stored in HashNodes class. A pixel represents either a root node, branch node or uncompressed tile.

Both of the below test applications used an abstract function (GetMapTile) to call an underlying data structure. I made sure both were using stack assigned variables.

Maybe I should make a lib out of it and post it on github or something. gprof results std::map name: GetMapTile(unsigned int, unsigned int) [rank]time%    self    children    called [2]    79.2     0.12    10.08        20,160,000        Core search lookup implementation name: std::map<unsigned int,tilemap::Tile>(...)::find() [rank]time%    self    children    called [4]    77.2    0.03    9.92        20,160,000             VS. Will's hash algorithm (WHA). name: GetMapTile(unsigned int, unsigned int) [rank]time%    self    children    called  [4]     42.0      0.33      6.14    20,160,000         Core search lookup implementation name: BinarySearch(std::vector<unsigned int, std::allocator<unsigned int> > const&, int, int, unsigned int) [rank]time%    self    children    called(+ recursive) [9]    18.2      2.52    0.58      11390744 (+75491000) Total Speed:   std::map (10.20 seconds) / WHA ( 6.47 seconds ) = WHA 40% faster. Memory storage: ***         Compression Test Results      *** Control struture: (std::map)   Size dimension: x=8400 y=2400   Total tile count:20160000   Size (MB):230   Map overhead (MB):400 (had to observe in process explorer)   Total memory (MB): 630

Branches structure: (WHA)   Size dimension (both x&y):20   Branches count:40470   Total tile count:6676135   Branches overhead (KB):2529   Size (MB):76   Total Size (MB):79 Total Compression/Memory efficiency = WHA has 87% smaller memory use

.

[willraman-blog]

1st data structure profile

Not as bad as I thought. Looking at the profiled data the biggest consumer of time is my UN-optimized use of SDL. The last entry on this list is the most promising that I am on the right track, 27,000,000 calls and tile retrievals from the data structure only took 0.12 of a second.

  %   cumulative   self         self      total            time   seconds   seconds    calls  ms/call  ms/call  name <Comment>

35.00      6.43      6.43       UNK                         inflateMark <SDL/DLL>

17.15      9.58     3.15     UNK                            inflateUndermine <SDL/DLL>

13.12     11.99     2.41    UNK                            pqdownheap <SDL/DLL>

3.48     12.63     0.64     UNK                        UM::Branch::GetSize()<stats info>

2.99     13.18     0.55 109967520  0.00    0.00  __mingw_pformat <sloppy>

2.78     13.69     0.51    UNK     __static_initialization_and_destruction_0(int, int)

2.78     14.20     0.51    UNK                              inflateCopy <SDL/DLL/Zlib?>

2.50     14.66     0.46 69600015    0.00    0.00  __gdtoa <too many types>

1.47     14.93     0.27 103947170  0.00    0.00  void std::vector<unsigned int*, std::allocator<unsigned int*> >::_M_insert_aux<unsigned int*>(__gnu_cxx::__normal_iterator<unsigned int**, std::vector<unsigned int*, std::allocator<unsigned int*> > >, unsigned int*&&) <creating the worldmap

0.63     16.32     0.12 27569449     0.00     0.00  UM::Branch::GetTile(unsigned char, unsigned char) <WOOT! Getting a tile is QUICK>

There are a few 0.5 second entries I can reduce with optimizing (I was sloppy). 

[willraman-blog]

The hash storage class

I figured I'd share the storage class I'm using now. Little bit more overhead (2mb more overall) for 6 million tiles. Yet look ups are quicker. Total tiles size in memory is 86 mb (including bloat).

This class has a derived logic class as a higher layer in the program to act as an intermediary between data and SDL pixel drawing functions.

// HashNodeClass.hpp

class HashNodes {     private:         Sint32 p2b;         Uint32 count;         Sint32 idlookup;         void resize(void);         Sint32 const getIndex( Uint32 const & hashlookup  );         std::vector<Tile> TileEntry;         std::vector<Uint32> Hash; // find on hash, get o(1) lookup on tile.         std::vector<Sint8> HasData; // -1 delete, 0 empty, 1 yes     public:         HashNodes();         virtual ~HashNodes();

        bool insert(Tile const & tl,Uint32 const & x , Uint32 const & y );         bool remove (Uint32 const & hashlookup);         Uint32 Count(void);         Tile const * get (Uint32 const & hashlookup) ;         void SortHash(void); };

High level summary:

1. On creation all 3 vectors are initialized to a power of 2 amount of entries in memory (128 to start with). 2. Insert pushes data onto the stack into each of the 3 vectors simultaneously. These entries are on a parallel index (VERY IMPORTANT). So, Tile[0] will always line up with Hash[0] value.

Tile entry - stores the tile class. Right now it just contains a color value and a few extra bytes to mimic the size of what I saw in Terraria memory format on one of those free server mods.

Hash - Value of the 1D location of the converted 2D (x,y). Necessary for binary search look ups.

Has data - This is used by the sort function to erase/ignore or check if data exists for retrieval.

3. Get() performs a binary search lookup on the sorted array against the hash value vector. When it finds a value that matches the 1d location of the tile requested, it returns the index of where the data was stored. Now the program performs an o(1) constant time look up to retrieve the tile and the hasdata.

4. Remove() sets values for deletion on the next sort.

5. SortHash() resorts all 3 vectors based on the hash values and erases any indexes that HasData equals -1.

6. Resize() - When the index amount on an insert surpasses pow(2,p2b) , it resizes all 3 arrays in memory to the next power of 2. Starting at 128 then 256 then 512. Etc.. For faster lookup on the binary searches.

Ran using this data structure last night. It takes about 30 seconds to load all 20,000,000 (2400x8400 map) into the same sized RGBA SDL surface for display.

I'm sure I have some more performance tweaks to make.

Then onto testing if this is faster then using a std::map.