text:
Do I really have to write my own optimized model format?
So I'm a brand new noob to the world of game dev and I'm starting off by trying to write my own game using C++ and openGL. I'm getting into loading models etc and while searching around for "the best format" I'm finding that most of the common formats are intended for porting between modelling applications and not necessarily for final representation of data when loading into a game environment. I'm being told through various sources that ultimately you want to use formats like collada etc and convert them into a custom binary format optimized for your game. Is this absolutely necessary? I understand the idea, that parsing a large XML or some other ASCII format is going to be slower than reading a binary file type but is it really going to be THAT big of a performance hit if I don't? I can't see it, but before I go and fill the assets directory of my game with dae or fbx files I thought I'd ask.

What's wrong with existing formats? They do perfectly fine for 99.9% of people.

What I believe these people are saying is that you want to load your COLLADA file into your in-game structure. You can then save the contents of this structure into a binary file ready for loading at runtime.
This can have advantages like the ones you said, but also has disadvantages, typically during the development stage.
Whether the load-time performance gain you get is necessary for your game is for you to decide. If you have a few non-complex models, the difference is probably negligable, and it is up to you to decide what to go with.
If for development purposes you prefer to use COLLADA and parse the XML at load time then go with it! I would recommend you make sure that your loading code is abstract enough so that you can easily replace it with binary files if the loading becomes too long.

So basically just do what I was doing and if I find it necessary I can use the SDK's for these formats to convert them to a final format for my game. Thanks for the clarification, it's hard sometimes to separate opinion. I've read a lot of criticism of using these formats (especially ascii) basically slamming them as something that would never be used in "professional" games but last I checked ID software has been using plain text models for the last 10-15 years.

How about deciding on a vertex layout and then storing this info in a file? Once you have this worked out you can work out what other similarities your meshes have. The problem I think you will face at first is the overwhelming number of slight differences each of your meshes has in it's requirements within the game world. Some of this information can be generated on model load however and may not be worth storing in the mesh 'data' file.


text:
Do any of the current gen console or handheld compilers support C++11?
I am not asking for full support but do any of the current gen support C++11? I know VS C++ supports lambda and the auto keyword and I believe gcc supports both as well. Do any of the current gen consoles or handheld (3ds, sony vita) support it?

This belongs on SO.

@Duck: I don't think so, these compilers are not widely available outside the game development community. If anything they are so locked down even anyone here who knows couldn't answer.

This is a very good question, if you're starting out on a project, and hope to be succesful you might dream of buying a PS3 or Wii devkit someday and port your game. Would be pretty painful if it turns out you're heavily relying on language features their compilers don't support.

I believe the Android toolchain supports C++0x.

Most of the major gaming consoles do not have public development kits, and forbid sharing much information about the underlying SDKs. They do tend to trail a few years behind other platforms for cost and stability reasons. If you have development kits for these consoles or the resources to get them, you should be able to contact your licensor for details on C++0x support.
So I can't answer for any of the major gaming consoles, but perhaps more important for independent development, the iOS toolchain does not. Xcode is still based on GCC 4.2, and they're moving forward by switching to Clang/LLVM, not newer versions of GCC. Clang keeps a feature matrix for C++0x support, and it's not nearly as complete as GCC's. Picking some major features, variadic templates, auto, and rvalue references are present, but constexpr, defaulted/deleted methods, and lambdas are not.

To add on, if you are an indie developer or part of a company looking to develop for a certain system, you could always contact the company and ask whether they support or plan on support certain languages.

Just as an update, the newest Clang does have some seriously complete C++11 feature support.

-1: Answer needs updating to reflect current Clang C++11 feature support.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
DirectX9 rendering missing in Release Build
I have a c++ application which outputs to screen using entirely DirectX9, running on Win7 64 Home.
It runs as normal in these circumstances:

Debug Build, from within MSVC 2008.
Release Build, from within MSVC 2008.
Debug Build, by opening the compiled
executable itself.

However, strange things happen when I run the compiled executable of the release build. The window is created as expected but no screen output. Nothing.
I can hear the sound working and the log file fills up. I thought maybe the working directory was wrong when running the executable but the log file reports the CWD is correct and indeed all filepaths to data files work.
I am stumped as to why my application will work fine in 3 of the four permutations, but not the most important one - the standalone release executable!
If anyone can contribute, I'd be most grateful.
Thanks
Si

the difference between running with the IDE attached at startup is usually that the state of the memory handed to you by the allocator is not the same. If I remember correctly, it's  zeroed out or filled with garbage (I can't rememeber which as we don't use standard allocators any more).
Checking memory should be your first approach vector. Make sure all your allocations assume that the memory is dirty and initialise them.

Attach the debugger to the version not started from within VS, and debug through to see what is going on. To help you catch the early part of the program, you can put a dialog box or __debugbreak into the early part so you can attach early and see the DX surfaces being created and so on.
Martyn

Thanks for the advice. Unfortunately as I already mentioned, the debug version works well from within MSVC and as an exe. Attaching to the release exe doesnt show me anything, as it is not built with debug info.

So you should enable building debug symbols for the release build [this is enabled by default in the IDE]. You can then debug the release one. Code generation is not impacted by building PDBs.

Follow Martyn's great advice and realize that you can use the debugger on anything, even running executables not built in "debug mode."  If you've turned on the symbols you can even load the EXE in the debugger and set breakpoints before you start the run.

Build your program with the highest warning level turned on, see if it catches any uninitialized variables.
Make sure that you're checking all return values from system calls.
Follow the advice to use the debug DirectX/D3D driver and watch its output to see what changes between the working code and the broken.

Please use DirectX SDK Utilities - DirectX Control Panel and see if you are not getting an error.
Set Debug level in control pannel, recompile your application and you should see runtime errors in the Output window

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
XNA and Matrix.<whatever>
I am not new to XNA 2D programming, but have never done 3D. I am interested in learning, but always get lost once I get to creating a Matrix.
I am sad to say that I don't really get them. Can someone explain, (or even just point me to a good tutorial) on getting started with matricies?
I understand them from a math point of view, but I don't really get the API. How do you use the API? What is the difference in CreatePerspecitive, and CreatePerspectiveFieldOfView. I am really looking for information in understanding when to use the different members the API provides.
I know this question is a little vague, and large, so I will try to edit it as needed.

possible duplicate of What is a good linear algebra book for game programmers?

I'm not asking for the math behind it, I asking on how to use the API

Not sure which aspects of Matrix math you're having difficulties with, so I'll list two books that helped me get over the 3D math hump. Chances are, you'll need to work through more than one book to get everything to finally "click".

3D Math Primer for Graphics and Game Development This is a great book, everything is explained thoroughly and in a language that's easy to understand. I would start here.
Mathematics for 3D Game Programming and Computer Graphics Another good 3D math textbook. Covers a wide range of material. It's concise and straight to the point.

I would start with these, even if you have to re-read the material a couple of times. I spent months going over 3D math topics before being comfortable with it.
EDIT: I posted this before you updated your question. If you're looking for help directly  with how to use Matrices in XNA, check out XNA Game Studio 4.0 Programming: Developing for Windows Phone 7 and Xbox 360 by Tom Miller & Dean Johnson (can't link, due to spam prevention, but it's on Amazon). Chapter 4 goes into the very basics of 3D Math and directly relate to the math classes in XNA. You'll probably learn a lot from the code samples in the later chapters as well.
EDIT 2: Another book that I recommend as well is Microsoft XNA Game Studio Creator's Guide. While this only covers XNA 3.0, the majority of it is still applicable to XNA 4.0. It not only has a chapter on Matrix math, but on creating a graphics engine camera system that shows great use of Matrices in XNA. I think you'd take away a lot from that sample.

awesome, I'll check it out. Here is the link for lazy people like me :) http://www.amazon.com/XNA-Game-Studio-4-0-Programming/dp/0672333457

Amazon link to the Microsoft XNA Game Studio Creator's Guide book. http://amzn.com/0071614060

I found that Riemers 3D XNA tutorials were great for picking up the basics on the matrices and how to use them specifically in an XNA environment.  The second tutorial makes a simple flight-sim so it also has a fair amount of instant gratification.
Here's a link to the first one, the navigation links are on the right side (something that threw me at first): http://www.riemers.net/eng/Tutorials/XNA/Csharp/series1.php

Just as a warning, I don't know if the tutorials have been updated for XNA 4.0 yet or not.

They have been updated to XNA 4.

I wrote a tutorial to specifically help with this :-)
It explains the concepts using Sunburn for XNA.
http://dsebj.evolvingsoftware.com/?p=211 [Matrix Math is Hard?]


text:
3D rotation math/code for plane
I am making a simple 3D game with plane in space.
With c++ (win32).
But the plane rotation is not realistic.
The code I am using for the rotation is the following:
point3D AxisRotation(point3D point,point3D Rotation){
float sx = Sin(Rotation.x*PI/180);
float cx = Cos(Rotation.x*PI/180);
float sy = Sin(Rotation.y*PI/180);
float cy = Cos(Rotation.y*PI/180);
float sz = Sin(Rotation.z*PI/180);
float cz = Cos(Rotation.z*PI/180);
float xy,xz, yx,yz, zx,zy;
xy = cx*point.y - sx*point.z;
xz = sx*point.y + cx*point.z;
yz = cy*xz - sy*point.x;
yx = sy*xz + cy*point.x;
zx = cz*yx - sz*xy;
zy = sz*yx + cz*xy;
point.x = zx;
point.y = zy;
point.z = yz;
return point;}

The axis of the rotation needs to be (Roll,Yaw,Pitch).
Does anyone know the code or the math for it ?
Thank you. Dave

For your convenience you might want to look into using matrices for your transformations. It will allow you to simplify your code. With respect to your question, have a look at this resource

Your question is unclear. Are you trying to determine the axis of rotation generated by this code? Or are you trying to write code which will rotate a point by a given angle around a given axis?

im trying to write code which will rotate a point by a given angle.
but the rotation needs to be an airplane rotation .. there is a differents rotation codes who made for different things..
im trying to do a rotation that will be similar to Fighter like this-> http://www.youtube.com/watch?v=GMsVBTHMK-M with giving the point position in - X Y Z ... and the angles by Roll Yaw Pitch
and will return the new X Y Z position
also thanks for caring :P

@Dave Then look at the resource I provided.

yes.. i was taking a look at the resource.. and i coded it.. but still there is a problem with the 3D rotation moving .. you can take a look at the game -> rghost.net/14012601 when your pressing UP ARROW key also the name of this rotation is Euler angles and people using it for camera rotation

To perform rotations in the (roll,pitch,yaw) basis, you need to know the aircraft's current orientation.

This comes up a lot on StackOverflow. What you ask is mathematically impossible. What you have in mind is quite simple, but you'll have to learn a little math and stop grabbing for the instant solution.

I think you need more than simple math to make this kind of rotation.. i think you need more of Plane Physics... this book has some details on how make a physically correct plane physics http://www.amazon.com/Physics-Game-Developers-David-Bourg/dp/0596000065/ref=sr_1_3?ie=UTF8&qid=1310548800&sr=8-3

Two obvious things w/o looking at the executable.. 1. Gimbal lock: this is what happens when 1 axis is "lost" due to axis parallelism (use Google for more on this, tons of indepth explanation), eulers are prone. Then again sensible airplane dynamics don't allow for a range of movement that allows this to occur. 2. Create a function that rotates a vector relative to an axis, makes it easier to handle "relative to orientation" rotations. And foremost what everyone else said.

Try this: (You'll need to call this three times, once for Roll, Yaw, and Pitch). This should work, I've used it in my own game, and it has been unit-tested. Of course, if your vector/point class has its overloaded operators defined differently then it may not give similar results. Here is my vector implementation (as of a few months ago).
point3D RotatePointAroundAxis( const point3D& axis, const float
                               radians, const point3D& point )
{
    float matrix[3][3];

    float sn = sinf(radians);
    float cs = cosf(radians);

    float xSin = axis.x * sn;
    float ySin = axis.y * sn;
    float zSin = axis.z * sn;
    float oneMinusCS = 1.0f - cs;
    float xym = axis.x * axis.y * oneMinusCS;
    float xzm = axis.x * axis.z * oneMinusCS;
    float yzm = axis.y * axis.z * oneMinusCS;

    matrix[0][0] = (axis.x * axis.x) * oneMinusCS + cs;
    matrix[0][1] = xym + zSin;
    matrix[0][2] = xzm - ySin;
    matrix[1][0] = xym - zSin;
    matrix[1][1] = (axis.y * axis.y) * oneMinusCS + cs;
    matrix[1][2] = yzm + xSin;
    matrix[2][0] = xzm + ySin;
    matrix[2][1] = yzm - xSin;
    matrix[2][2] = (axis.z * axis.z) * oneMinusCS + cs;

    return point3D
    (
        matrix[0][0] * point.x + matrix[0][1] * point.y + matrix[0][2] * point.z,

        matrix[1][0] * point.x + matrix[1][1] * point.y + matrix[1][2] * point.z,

        matrix[2][0] * point.x + matrix[2][1] * point.y + matrix[2][2] * point.z
    );
}

If you're trying to rotate an entire plane then I suspect you have a rotation matrix, if you're using DirectX you could use something like D3DXMatrixRotationRollYawPitch(&mRotation, rotation.y, rotation.x, rotation.z); I'm not sure if that's the exact function name.


text:
Turning a sprite such that it rotates in the direction that's most efficient
I have a sprite that moves from waypoint to waypoint. It turns to face its velocity vector, but not instantly (there's a rotation speed).
The problem I'm having is, from one direction to another, the sprite will often turn in wild, unnecessary ways instead of appearing like you might expect a car to appear (turn such that the minimum delta in angle occurs).
Right now I'm using the following formula to calculate the rotation float for the current velocity:
MathHelper.PiOver2 + -Math.Atan2(anotherVector.Y - vector.Y, -(anotherVector.X - vector.X));

And then I lerp the current rotation by the new rotation by the rotation speed (10f):
rotation = MathHelper.Lerp(rotation, targetRotation, 10f * (float)gameTime.ElapsedGameTime.TotalSeconds);

But unfortunately, it's causing the sprite to spin in wild directions before reaching the correct angle. Any suggestions?

Shouldn't the 3rd parameter for lerp, the time, be between 0 and 1?

possible duplicate of Calculating angle between 2 vectors

This is due to the angle wrapping. For example, lerping from 1 degree to 359 degrees is not what is wanted, instead the equivalent lerp from 1 degree to -1 degree should be used. If the angles are in the same range, then adding or subtracting 2*pi to the target will work, e.g.
if (targetRotation > rotation+Pi)
    targetRotation -= 2*Pi;
else if (targetRotation < rotation-Pi)
    targetRotation += 2*Pi;

It's important that the angles are in the same range. The [-pi,pi] range returned by atan2 is the most standard, so I'd recommend using that for all angles if possible. Whatever range is chosen, wrap the rotation back into that range after lerping.

The function MathHelper.WrapAngle is useful for this.

I think you should replace the ifs with whiles. what if one of them is 100040 degrees and the other is 10?


text:
How can I have my game engine track player history?
I'm in the very early stages of designing a browser-based text RPG. The project is basically just something I'm doing for fun and as a learning experience. I'm starting to wrap my head around the infrastructure of the game and I keep getting hung up on the best way to accomplish this.
If I have a map comprised of a grid with different items/monsters/quests/etc. in each 'tile', what's the best way to keep track of the areas on the grid where the player has been?
If the map is a grid of 1000x1000 squares, I want to know that in the player's entire gaming history, they have already visited squares A-1, F-6, GQ-46, etc. This list could be huge for each and every player.
Along the same lines, if I have quest-dependant events, how do I track the quests players have completed? Each player would need to have something letting the engine know if they have or have not completed potentially hundreds of quests.
My first idea was to save this information somehow in each player entry in the database, but that would mean a field for every one of the tiles in the 1000x1000 map. That doesn't seem like it would scale.
I'm just not sure how to store the info that lets the engine say "hey, I know that out of all the tiles on the map, this player has been on this particular one before." or "out of all the quests, this player has completed this particular one".
What is the best way to approach this?

You need a good book on relational databases and SQL; it's clear you don't know how to use them. Sorry to be so blunt about it. To represent the relationship between players and the tiles they've visited, you would have a table like player_tiles, with two columns, player_id and tile. For each title a player visits, you insert one row. You'd have a similar table relating players to quests they've completed. That is the minimal representation of the information you need to store.

Dan - that's a fantastic way to approach it. I have used that concept before once or twice but didn't think to use it here. And no, I'm not an expert with databases - that's why I am doing this, to learn. And look, thanks to you, I already learned something :)

@Cail - I don't think that Dan's idea is quite something you'd want to use for a game. Especially if you're actually going to have a map thats 1000x1000 or more. Consider that if each player walked over every tile, you would have 100 000 records for EACH player in that table. Not only that, but I'm assuming you'd want to use that data somehow in your game which means looping through all records for each player. It may work fine initially, but I don't think it will scale well. On the other hand, using the method outlined by Patrick (using a bit-map) might be more efficient/effective for you.

Since your map is a grid of fixed size and all you want is "has been visited", for the first part you can use a bit-map.  For a 1024x1024 grid your storage size would be 128K and very fast to look up and small enough to keep in memory if you need super fast access (for fog of war rendering, or info overlays).
The quest info could be done two ways.  It would be pretty easy to store them in a database and run queries as needed, and probably the best solution overall, @Dan Grossman
The other method would be to generate a hash from the quest information then simply store a list of hashes that the player has completed.  Storage would grow dynamically, hash lookup at run time is very fast, and new quests could be added whenever you wanted.

+1 I really like that bit-map idea. I think I may use it in my game.

@RichardMarskell-Drackir you should read up on adjacency matrices, they will give you some idea on implementation. (Also see http://stackoverflow.com/a/5419933/431528)

A database seems like overkill.  As @Patrick Hughes says, a bitmap is a great choice for map coverage plus 'fog of war' implementations.  Bitmaps can also be used to track true/false conditions of game story.  For example, you might have a list of ids or an enum that map to game events, like
enum GameEvents {
    VisitedTheTown = 1,
    KilledTheOgre,
    SavedThePrincess
}

Then you can do BitMap.Set(GameEvents.KilledTheOgre); when that action happens, and you can query for it later if some dialog tree depends on it.  It's also efficient to store in your save game since it's only 1 bit for every yes/no game event state.  You just don't want to be adding/removing items from the middle of your enum if you want different versions of your saves to be compatible.
Another approach is to use a data structure called a Blackboard.  Implementation is up to you but it's often like a cross between a property bag and the Windows registry.  You can store yes/no conditions like in a bitmap but you can also store strings or quantities (for the ever popular "Kill 10 kobolds" quest).
Here's a link:
http://aigamedev.com/open/article/static-blackboard/
And a book that mentions the subject:
AI Game Programming Wisdom

It would not be a 'bit map' as such if you can store more than... well, a bit in each field. But the idea remains, as many solutions will probably store a byte for each field anyway, you can store a lot of information in those 8 bits :).

@Daniel, it's exactly a bit map:  if bit 1 is set, VisitedTheTown is true, if bit 2 is set, KilledTheOgre is true.  Unset bits are false conditions.  In a map sense, a set bit might be an explored tile or sector.  Storing quantities requires a different data structure as I said.

A database is an excellent tool for something like this, storing it in any other way would force you to (partially) recreate what a database already solves for you. As was mentioned by Dan in comments, using a relational table that maps the players id to the cell id that has been visited is a good solution. Databases are built for just this sort of thing and querying it for if a cell has been visited is a fast operation.
If database storage is costly for you (which it might be on a hosted solution) you can consider compressing the number of fields somewhat. In the case of "has this cell been visited" you would normally be forced to travel through the areas sequentially, so to get from A1 to A3 you would have to pass through A2 (or go a path around A2 depending on terrain).
You can use this fact by storing strips into the database instead of each cell individually, for instance (player, row, firstHorizontal, lastHorizontal), this way you can find out if a player has been in a cell by:
select * from VisitedAreas where player=@playerID and row=@row and firstHorizontal<=@column and lastHorizontal>=@column

The update method would be more complicated in this case however, you would have to look for a strip that is next to the current cell and if one is found, update either first or lastHorizontal field as appropriate, or if one isn't found you add a new strip where first and lastHorizontal is the current location.
Quests can be solved in a similar way, (playerID, questID, progress), progress can either be a foreign key to a "QuestSteps" table or you could go the oblivion/skyrim approach and store a number from 0 to 100 for every quest that maps to what you have done so far, for instance:
10 - accepted quest
11 - killed 1 goblin
12 - killed 2 goblins
15 - found the necklace in the chest
20 - returned necklace
30 - discovered the necklace wasn't the questgivers
40 - killed the questgiver and retrieved the necklace
100 - returned the necklace to the goblin owner

Again, if you wish to reduce the number of fields per player you can lump quests together by area, in many cases the player would probably finish all quests in a region before moving on to the next. In this case you can have a RegionCompleted (playerID, regionID), while a player is working on the quests in a region this is blank and you check the "QuestCompetions" (playerID, questID, progress) table for each individual quest, once all quest are completed however you add a row to the "RegionCompleted" table to mark this, and then remove the rows that correspond to that region from the "QuestCompletions".
Hope this helps.


text:
Logic behind a bejeweled-like game
In a prototype I am doing, there is a minigame similar to bejeweled. Using a grid that is a 2d array (int[,]) how can I go about know when the user formed a match? I only care about horizontally and vertically.
Off the top of my head I was thinking I would just look each direction. Something like:
int item = grid[x,y];
if(grid[x-1,y]==item)
{
    int step=x;
    int matches =2;
    while(grid[step-1,y]==item)
    {
        step++;
        matches++
    }
    if(matches>2)
        //remove all matching items
}
else if(grid[x+1,y]==item
    //....
else if(grid[x,y-1==item)
    //...
else if(grid[x,y+1]==item)
    //...

It seems like there should be a better way. Is there?

I remembered I wrote tedious for loop to do that (for a connect-n)

Loop through each item in the same axis (x or y), if they are the same as the previous item them increment matches. When the next item becomes different, check if matches is or greater than 3, call a function that removes matching items, and continue.
AS3 code:
var grid:Array = [[2,3,2,2,2,4],
                  [ .. ]]; //multidimensional array
var matches:uint;
var gemType:uint;
for(col = 0; col < grid.length; col++){
    matches = 0;
    gemType = 0; //Reserve 0 for the empty state. If we make it a normal gem type, then only 2 are needed to match for the start.
    for(i = 0; i < grid[0].length; i++){
        if(grid[col][i] == gemType){
            matches++;
        }
        if(grid[col][i] != gemType || i == grid[0].length - 1){ //subtract 1 because arrays start at 0
            if(matches >= 3){
                removeMatches(blah);
            }
            gemType = grid[col][i];
            matches = 1;
        }
    }
}

This is only for the x axis, for y, grid[col][i] would become grid[i][row], etc. I'm sure you can figure that out :)

Very old post I know, but wanted to point out the flaw in removing items as soon as a match is found. If you had a match along the x-axis you can still potentially have a match on the y-axis that may utilize one of the same tiles. Removing the first match breaks the other from being found.  I would flag all matches then remove them after the entire puzzle has been searched.

Just thought I'd weigh in with our experience in building a Match-3-like game.
We have built a prototype for a Match-3 based word game, a little like mashing up scrabble and Bejeweled. We realized very early on that the engine that supplies new gems/tiles to fill empty spaces would have to be highly introspective (we run hybrid heuristics and MonteCarlo sampling) in order to create actual opportunities for a player to string letters to form words through the Match-3 mechanic. It's way more elaborate than the description but I'm keeping it brief because we'd have to write a paper.
To answer the OP -- we are doing pattern checks to score how many matches there are on any given gird, at the current time, through a method very similar to "gladoscc" code snippet. While it works robustly, the computational cost for running that recursively during the tree-search play-out becomes a substantial burden, so we are in the process of rewriting this portion of the logic and the data-representation with the bit-board methodology (commonly implemented in other-grid like games like chess, checkers, Othello, etc.) In tests we have shown that it can run over 20 times faster in ActionScript, and so for us the need to do it is a slam-dunk -- and frees up essential cycles for responsiveness, sound, animation, etc.

Your answer should be an answer and not adding another question. If you have a question, please create a new question using the "ASK QUESTION" button. This is not a discussion forum.

bummzack.... thank you for that. My rationale was that we had an insight to offer, especially as it relates to the performance of what was earlier proposed when tree-search/introspection was added to the context. And it continued to be relevant since we're still talking essentially about the "Logic behind a Bejeweled game". If this continues to be bad-form, I will be happy to edit/re-post as per your advice.

That's fine. But you should remove the "question" part from your answer. Questions should be new questions and not part of an answer...

edited and posted the question elsewhere

Recursion, yo.  It's for when you don't know your boundaries.
   public int getHMatchSize(int row, int column)
    {
        int returnMe = getMatchValue(row, 0, column, 1);

        if (returnMe < 3)
        {
            return 0;
        }
        else return returnMe;
    }

    public int getVMatchSize(int row, int column)
    {
        int returnMe = getMatchValue(row, 1, column, 0);

        if (returnMe < 3)
        {
            return 0;
        }
        else return returnMe;
    }

    /// <summary>
    /// I return the match size.
    /// </summary>
    /// <param name="row"></param>
    /// <param name="rowDelta">1 means look vertically.  Dont set both deltas to 1.</param>
    /// <param name="column"></param>
    /// <param name="columnDelta">1 means look horizontally.  Dont set both deltas to 1.</param>
    /// <returns>The number of contiguous matching things</returns>
    public int getMatchValue(int row, int rowDelta, int column, int columnDelta)
    {
        int[] start = getEndItem(row, -1 * rowDelta, column, -1 * columnDelta);
        int[] end = getEndItem(row, rowDelta, column, columnDelta);

        int returnMe = 0;
        returnMe += end[0] - start[0];
        returnMe += end[1] - start[1];
        return returnMe;
    }

    /// <summary>
    /// I will return the end of a sequence of matching items.
    /// </summary>
    /// <param name="row">start here</param>
    /// <param name="column">start here</param>
    private int[] getEndItem(int row, int rowDelta, int column, int columnDelta)
    {
        Gem matchGem = new Gem(-1);
        int[] returnMe = new int[2];

        if (boardSpace[row + rowDelta][column + columnDelta] == boardSpace[row][column])
        {
            return getEndItem(row + rowDelta, rowDelta, column + columnDelta, columnDelta);
        }
        else
        {
            returnMe[0] = row;
            returnMe[1] = column;
            return returnMe;
        }
    }

You can use the flood fill algorithm.
It's really useable to this type of problem.

No, actually it has nothing to do with the Question. The OP is asking how to detect three matching items in a row.

If you start the fill with the flipped element(s), the algorithm goes through the matching elements.
But just to check 3 (and no more) matching element in a row (and no crossing columns), it is maybe an overkill.
We use this in a Bubble Puzzle like game, and does exactly what we need.

You should maybe explain a bit more than just "use the flood fill" because I was confused for a second how that is relevant to this problem.


text:
AI for solving a Match 3  game
Is there a known good way to have a "computer" opponent play a Match 3 game? It doesn't have to be fancy, or even considered fair. If the AI always takes the best move on the board that would be OK with me. Note that a valid move is one that doesn't make a match.
Edit:
What I am currently doing is a brute force approach. I look at every tile on the board, and see what the best move that tile can do. I add it to a collection and give it a score (based on how many it will match 3 or 4). Once I have traversed the entire board I use the move with the  best score. In the event of a tie I pick one.
If a 5 match combo is found I short circuit out to that one. 5 is the highest combo you can get)
I may not be able to improve it, but it feels like this should have been solved already.

This type of game is known as "Match 3". That might help you find more results.

awesome. thanks for that :) "bejewled-like" doesn't help much

One approach would be a simple tree-search algorithm, similar to the methods used for many deterministic puzzles.
The first problem is that the new gems added with each move are non-deterministic. One way to handle that is to consider all the possibilities for each new gem. This gives a way to estimate probabilities.
The big problem is that the number of combinations to consider would be immense, even a small number of moves into the future. The solution to that is to use heuristics to prune the tree, and to guide the search. For the random gems, only consider a small random selection of the possibilities.
For more tips and more detail, Google for tree search nondeterministic games.
http://www.google.com/search?q=tree+search+nondeterministic+games
On second thoughts, try tree search nondeterministic puzzles.
http://www.google.com/search?q=tree+search+nondeterministic+puzzles
Also, remember to keep it simple - there's probably very rapidly diminishing returns in Bejewelled, either for deeper searching or for more sophisticated heuristics.

Considering Bejeweled doesn't allow you to make a move that doesn't involve a match, couldn't you just figure out all subset of legal moves (you should already have this functionality if you prevent the player from making non-matching moves) and just pick the one that would give you the most points?  From my understanding there isn't a ton of skill in Bejeweled as you're mostly at the whim of what the random number generator picks for your filler blocks.
Are you trying to design something more complicated like Puzzle Quest where looking ahead actually matters?

+1 - but there is some room for lookahead-based strategy in bejeweled. First, you get some new random gems with each move, but they don't replace all existing gems - some of the next few states is predictable. Second, where there's a choice of moves, some will result in more new random gems than others - depending on the current state, perhaps more randomizing is better, or perhaps preserving more is better. Finally, there may be heuristic-based ways of increasing the chances of creating higher scoring opportunities in the future, though many players heuristics probably don't really work.

Yes, you can make moves that do not form a match.

If you can make moves that don't form a match then it's not very Bejeweled-like, and the mechanisms for determining what you can do are going to be a lot more complicated.

@Joe: So, it's basically my favorite game of all time, Tetris Attack?

to an extent. It is really a mini game in an RPG I'm working on. (think of the card games in the FF series). You and the computer share a board and take turns making moves (3 per turn). you get points for matching the items, and combos.


text:
How to implement time traveling into a game?
I was wondering how to implement time travel into a game. Nothing super complex, just time-reversal like what's in Braid, where the user can rewind/fast forward time by 30 seconds or whatever.
I searched around the web a lot, but my results usually referred to using time as in like "it's 3:00" or a timer and such.
The only thing I could think of was using 2 arrays, one for the player's x position and the other for the player's y position, and then iterating through those arrays and placing the character at that position as they rewind/fast forward time. Could that work? If it would work, how large would the array have to be and how often should I store the player's x and y? If it doesn't work, what else could I try?
Thanks in advance!

Don't you read the news (http://www.ust.hk/eng/news/press_20110719-893.html)?  They've just shown that time travel is not possible.  Therefore, it's impossible to code.

You need to think a possible semantics for time-travel, only afterwards you can start to think about implementation.

http://en.wikipedia.org/wiki/Time_travel

Learn yourself some vector math. If you're proposing two separate arrays that suggests you've never worked with them. I consider them vital for a games programmer to know because of how much they can simplify things.

import universal.back2future.FluxCapacitor;

https://www.youtube.com/watch?v=8dinUbg2h70

https://news.ycombinator.com/item?id=9484197

The array idea is pretty much how it was implemented in Braid. When the only things acting on a character are gravity, keyboard/joypad input, and other characters, you pretty much only need to store the position and the velocity at each step to know everything important about that character. If you store 10 snapshots per second per character then it's still less than 50K for a minute of one character's history - easily manageable on most systems, and you can find ways that are more efficient than that too.

This is the right track. For example store active commands : keypresses with timestamps. You can extrapolate most other behavior if the system is deterministic. 10 fps tracker is fine for a rewind system, even less might be acceptable, as long as the actual commands are retained, in effect the state or statechanges of the objects.

Read up on the Command Pattern.  It provides for undoing actions (and for later re-doing them.)  That would handle more than just position of a ship, but all actions the player takes.
But I think your array idea is sound as well.

Probably not a great idea - besides being more memory-intensive (every time you add an entity's velocity to its position, you need to store that as an "action"), it pretty much requires fixed-point math, since if you use floating-point for your positions/speed, (x+v)-v might not be equal to x.

@BlueRaja - Don't see where that approach would be memory-intensive. At 100 FPS and storing the last 10 seconds, you need to store 1000 n-tupels of commands, where n is at most 5 or so. Or, even better, you store only the absolute position in each of those frames, and for the rewind, you simply animate the character backwards along that path. That would also eliminate any possible floating point issues and brings you back exactly to where you started.

Rather than have two separate arrays, you should probably have one class that describes the player's position (there's probably a Point class in Java already... I'm a C# guy lately) and use one single array to hold past positions.
You need to setup a "ring buffer", meaning that when you get to the end of the array, you circle back to the beginning of the array, overwriting the oldest entries.  If you travel back in time, the opposite is true (when you get to the beginning, circle up to the end).
If you want to hold 30 seconds worth of past data, you need to know your frame rate if you want to pre-allocate space and use a fixed-size array.  If you render the game at 10 frames/second, times 30 seconds, that's 300 elements.

GDCVault has a lecture by Jon Blow (the creator of Braid) on their site called The Implementation of Rewind in Braid for $3.95.  I'll bet this has the info you want ;)
EDIT:  Probably won't be in Java but the ideas should hold.

Do you know if they sell the transcript too, or only the audio?

I couldn't find anything via a quick search of the site.  Maybe you could use some transcription software?

Like Erik J said, storing the player's past positions as a collection of point objects in a ring-buffer sounds reasonable.
However, I would suggest using a queue to implement the buffer. It's much cheaper to update than an array and you don't have to know your frame rate in advance:
update():
   time_queue.push(player.positions)
   if current_time() - start_time > n:
       queue.pop()

This does not yet consider varying frame rates or what should happen if you actually do any time-traveling, so I suggest you store a time stamp with each entry and check that instead:
update():
    time_queue.push({
        'pos': player.positions,
        'time': current_time()
    })
    first_entry = queue.peek()
    while current_time() - first_entry['time'] > n:
       queue.pop()
       first_entry = queue.peek()

Hope this helps!

There's a design pattern called Memento, I think it's a starting point for a game like Braid

The memento pattern is a software design pattern that provides the ability to restore >an object to its previous state (undo via rollback).
The memento pattern is used by two objects: the originator and a caretaker. The originator is some object that has an internal state. The caretaker is going to do something to the originator, but wants to be able to undo the change. The caretaker first asks the originator for a memento object. Then it does whatever operation (or sequence of operations) it was going to do. To roll back to the state before the operations, it returns the memento object to the originator. The memento object itself is an opaque object (one which the caretaker cannot, or should not, change). When using this pattern, care should be taken if the originator may change other objects or resources - the memento pattern operates on a single object.

http://en.wikipedia.org/wiki/Memento_pattern
Adcional info here: http://dofactory.com/Patterns/PatternMemento.aspx

I fail to see how this should help. Looks like it is a "instant-rollback", while the OP asked for something smooth like Braid's one. Maybe I misread something?

This is pattern not implies on a single rollback, you can create a "timeline" of actions, for example.
Here's an Brazillian's blog post about that usage of this pattern:
http://abrindoojogo.com.br/padroes-de-projeto-memento
Here's an example made in Flash: http://abrindoojogo.com.br/files/fasteroids.swf
Move: Arrows | Shoot:Space | Rewind Actions:Backspace

There was a game released for the XBox360 that involved time-manipulation. It was mediocre, so I can't remember the title at this time. Anyway, in an interview with a developer for it, they outlined how they managed time manipulation:
Every X frames (with lower values of X leading to more fine-grained manipulation), you take a "snapshot" of the gameworld at that point, and associate it with an in-game time.
While playing through the game normally, time-forward, every input an reaction contributes to the snapshot set at some time in the future.
The game world then iterates between the snapshot at the current time, and the snapshot X frames in the future.
Then, when you want to reverse time, just set the direction of time to be backwards, so that it is iterating between the present and the snapshot X frames in the past (while disabling the ability to create future snapshots).

+1 for the point about the granularity of the snapshots.

You can simply treat the game's virtual time as another space-like dimension. So what's time travel from the outside is a simple n+1 dimensional movement in the game's virtual universe.
Assuming some user interaction and some sort of physics system that determine the behaviour of your universe when there's no user input, all you need to record is the effect of user interactions (for example, changes in the n+1 dimension speed/acceleration vectors), as your physics should be time-reversible.
This way you'd need much less memory to calculate the state of the game universe at any given time coordinate.

As I mentioned in another comment, physics in video games is usually not time-reversible, because when using floating-point numbers, (x+v)-v might not be equal to x

Let's say an entity has a velocity, rotation, x and y position. These are, with acceleration, the basic movement states, values, whatever you call it.
You can save the data in two ways:
1. Save rotation, x and y position
2. Save rotation, x velocity and y velocity
If you have a fixed velocity, you could also only save rotation, or save only one velocity for both axis.
Saving rotation is necessary in games, unless your entity has a static rotation, what it is not in most cases.
That said, using a list of objects for multiple values is necessary. If you have a nice timer system, which, for example, calls update methods 20 times in a second, and therefore is fps independent, you can create an array of 20 * 30 objects to store the movement values you need for the last 30 seconds. Using a simple array is not recommended, since you would have to move every element one index left each update call.
Based on this, you can go through the list or whatever to go back. If you really want to gain a "realistic" effect, use this technique for all moving objects. But this is game design related.
If you destroy objects, remember to pool them, to ensure that you do not stress your neat friend Mr. Garbage ;)


text:
How to include fur in the exported obj file in Maya?
In Maya I use fur to create plants. In my game I want to render these plants with cel shading. I use Wavefront .obj as a file format in my game for the models, but it doesn't seem to include the fur.
Is there a way to export the fur (as vertices) with the model into the obj file? Generating the fur at runtime is a bit CPU expensive for the platform.

Fur is usually implemented as a render effect -- there isn't a 1:1 correspondence with geometry, although geometry may be used to achieve the effect (textured polygonal strips, for example, or the newer and better looking 'shells and fins' methods), so there isn't really anything to export unless you were you convert the fur representation to 3D geometry. This would almost certainly result in extremely poor performance in your game.
The solution you probably want to is abandon using Maya to generate the foliage and employ a rendering effect in your game code to achieve the desired results instead. The article I linked to before provides one possible implementation; here is another example, using XNA.
However, since you said you are using Maya's fur rendering to produce plants, you may instead want to consider rendering algorithms designed for exactly that effect. Game Rendering has a whole section on "vegetation." There's quite a few options for grass rendering, for example:

Rendering Grass with Instancing in D3D10
Rendering Countless Blades of Waving Grass

I know you mentioned being CPU limited, but you didn't specify exactly how much so, or what the GPU resources you have available are. It should be reasonable these days to implement some level of these techniques with reasonable scalability back to older hardware and without too much CPU strain.
If that fails, you can always fall back to using simple polygonal billboard strips and "exporting" your fur out of Maya by rendering it as a texture you eventually apply to the billboards in your game. But actually exporting the fur as geometry is almost certainly not the approach you want.


text:
Is there any documentation comparing/contrasting C++ standard library implementations?
(This is not game programming per se, but I'm certain if I asked this on SO I'd get told not to prematurely optimize, even though history tells us every large game ends up worrying about these things.)
Is there a document anywhere that summarizes the differences in performance, and particularly memory usage, between different C++ standard library implementations? The details of some implementations are protected by NDA, but a comparison between even STLport vs. libstdc++ vs. libc++ vs. MSVC/Dinkumware (vs. EASTL?) seems like it would be immensely useful.
In particular I'm looking for answers to questions like:

How much memory overhead is associated with the standard containers?
What containers, if any, do dynamic allocations merely by being declared?
Does std::string do copy-on-write? Short string optimization? Ropes?
Does std::deque use a ring buffer or is it crap?

I was under the impression that deque was always implemented in the STL with a vector.

@Tetrad: Until a few weeks ago I was too, but then I read it was often implemented by a rope-like structure - and that seems to be what's in STLport.

The STL has an open working-draft, which can be used to find information regarding the various data structures (both sequential and associative), algorithms and helper classes implemented. However, it appears to be the case that memory overhead is implementation specific, rather than specification defined.

I can see this being a good question, but it's not related to gamedev at all..

@Duck: Game development is the only place I'm aware of that regularly uses high-level C++ features yet needs to meticulously track memory allocations because it runs on low-memory no-virtual-memory systems. Every single answer on SO would be "don't prematurely optimize, the STL is fine, use it!" - 50% of the answers here so far are that - and yet Maik's test clearly shows a major concern for games wishing to use std::map, and Tetrad's confusion and mine about common std::deque implementations likewise.

(That being said, if you think it's off-topic, you should vote to close.)

@Joe, whilst it is true that whilst game-developing you need to optimize as much as possible. If you need the functionality of a certain STL container, then you either use the STL container, or create your own. The latter being, most likely, the least optimized, so whilst you should take note of things like this, there are other things that will most likely be better to optimize. :)

@Joe Wreschnig I don't really want to vote to close because I'm interested in the outcome of this. :p

@Joe: If std::map allocates memory by being declared... what does it matter? It's not like you create a std::map and just forget about it; you create a map in order to put things into it. I don't see how that is a "major concern for games". Similarly, what does it matter exactly how std::deque is implemented? You use a deque when you need its peculiar bag of tricks: fast head/tail insertion combined with fast random access and rare iterator invalidation. How often does that one come up in game development?

@Nicol the allocation on declare can be a problem when using global objects, whose constructors are called before the main entry point of the app. Some platforms do not provide heap memory out of the box, you have to initialize it at program start, but the ctors for the globals were already called at that point, so their heap allocations failed

In case you don't find such a comparison chart, the alternative is to inject an own allocator to the STL classes in question and add some logging.
The implementation I tested (VC 8.0) uses no memory allocation just by declaring a string/vector/deque, but for it does list and map. The string has a short string optimization, since adding 3 chars didn't trigger an allocation. The output is added below the code.
// basic allocator implementation used from here
// http://www.codeguru.com/cpp/cpp/cpp_mfc/stl/article.php/c4079

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <map>

template <class T> class my_allocator;

// specialize for void:
template <>
class my_allocator<void>
{
public:
    typedef void*       pointer;
    typedef const void* const_pointer;
    // reference to void members are impossible.
    typedef void value_type;
    template <class U>
    struct rebind
    {
        typedef my_allocator<U> other;
    };
};

#define LOG_ALLOC_SIZE(call, size)      std::cout << "  " << call << "  " << std::setw(2) << size << " byte" << std::endl

template <class T>
class my_allocator
{
public:
    typedef size_t    size_type;
    typedef ptrdiff_t difference_type;
    typedef T*        pointer;
    typedef const T*  const_pointer;
    typedef T&        reference;
    typedef const T&  const_reference;
    typedef T         value_type;
    template <class U>
    struct rebind
    {
        typedef my_allocator<U> other;
    };

    my_allocator() throw() : alloc() {}
    my_allocator(const my_allocator&b) throw() : alloc(b.alloc) {}

    template <class U> my_allocator(const my_allocator<U>&b) throw() : alloc(b.alloc) {}
    ~my_allocator() throw() {}

    pointer       address(reference x) const                    { return alloc.address(x); }
    const_pointer address(const_reference x) const              { return alloc.address(x); }

    pointer allocate(size_type s,
               my_allocator<void>::const_pointer hint = 0)      { LOG_ALLOC_SIZE("my_allocator::allocate  ", s * sizeof(T)); return alloc.allocate(s, hint); }
    void deallocate(pointer p, size_type n)                     { LOG_ALLOC_SIZE("my_allocator::deallocate", n * sizeof(T)); alloc.deallocate(p, n); }

    size_type max_size() const throw()                          { return alloc.max_size(); }

    void construct(pointer p, const T& val)                     { alloc.construct(p, val); }
    void destroy(pointer p)                                     { alloc.destroy(p); }

    std::allocator<T> alloc;
};

int main(int argc, char *argv[])
{

    {
        typedef std::basic_string<char, std::char_traits<char>, my_allocator<char> > my_string;

        std::cout << "===============================================" << std::endl;
        std::cout << "my_string ctor start" << std::endl;
        my_string test;
        std::cout << "my_string ctor end" << std::endl;
        std::cout << "my_string add 3 chars" << std::endl;
        test = "abc";
        std::cout << "my_string add a huge number of chars chars" << std::endl;
        test += "d df uodfug ondusgp idugnösndögs ifdögsdoiug ösodifugnösdiuödofu odsugöodiu niu od unoudö n nodsu nosfdi un abc";
        std::cout << "my_string copy" << std::endl;
        my_string copy = test;
        std::cout << "my_string copy on write test" << std::endl;
        copy[3] = 'X';
        std::cout << "my_string dtors start" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "vector ctor start" << std::endl;
        std::vector<int, my_allocator<int> > v;
        std::cout << "vector ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            v.push_back(i);
        }
        std::cout << "vector dtor starts" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "deque ctor start" << std::endl;
        std::deque<int, my_allocator<int> > d;
        std::cout << "deque ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            std::cout << "deque insert start" << std::endl;
            d.push_back(i);
            std::cout << "deque insert end" << std::endl;
        }
        std::cout << "deque dtor starts" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "list ctor start" << std::endl;
        std::list<int, my_allocator<int> > l;
        std::cout << "list ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            std::cout << "list insert start" << std::endl;
            l.push_back(i);
            std::cout << "list insert end" << std::endl;
        }
        std::cout << "list dtor starts" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "map ctor start" << std::endl;
        std::map<int, float, std::less<int>, my_allocator<std::pair<const int, float> > > m;
        std::cout << "map ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            std::cout << "map insert start" << std::endl;
            std::pair<int, float> a(i, (float)i);
            m.insert(a);
            std::cout << "map insert end" << std::endl;
        }
        std::cout << "map dtor starts" << std::endl;
    }

    return 0;
}

So far VC8 and STLPort 5.2 tested, here is the comparison
(included in test: string, vector, deque, list, map)
                    Allocation on declare   Overhead List Node      Overhead Map Node

VC8                 map, list               8 Byte                  16 Byte
STLPort 5.2 (VC8)   deque                   8 Byte                  16 Byte
Paulhodge's EASTL   (none)                  8 Byte                  16 Byte

VC8 output string/vector/deque/list/map:
===============================================
my_string ctor start
my_string ctor end
my_string add 3 chars
my_string add a huge number of chars chars
  my_allocator::allocate    128 byte
my_string copy
  my_allocator::allocate    128 byte
my_string copy on write test
my_string dtors start
  my_allocator::deallocate  128 byte
  my_allocator::deallocate  128 byte

===============================================
vector ctor start
vector ctor end
  my_allocator::allocate     4 byte
  my_allocator::allocate     8 byte
  my_allocator::deallocate   4 byte
  my_allocator::allocate    12 byte
  my_allocator::deallocate   8 byte
  my_allocator::allocate    16 byte
  my_allocator::deallocate  12 byte
  my_allocator::allocate    24 byte
  my_allocator::deallocate  16 byte
vector dtor starts
  my_allocator::deallocate  24 byte

===============================================
deque ctor start
deque ctor end
deque insert start
  my_allocator::allocate    32 byte
  my_allocator::allocate    16 byte
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
  my_allocator::allocate    16 byte
deque insert end
deque dtor starts
  my_allocator::deallocate  16 byte
  my_allocator::deallocate  16 byte
  my_allocator::deallocate  32 byte

===============================================
list ctor start
  my_allocator::allocate    12 byte
list ctor end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list dtor starts
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte

===============================================
map ctor start
  my_allocator::allocate    24 byte
map ctor end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map dtor starts
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte

STLPort 5.2. output compiled with VC8
===============================================
my_string ctor start
my_string ctor end
my_string add 3 chars
my_string add a huge number of chars chars
  my_allocator::allocate    115 byte
my_string copy
  my_allocator::allocate    115 byte
my_string copy on write test
my_string dtors start
  my_allocator::deallocate  115 byte
  my_allocator::deallocate  115 byte

===============================================
vector ctor start
vector ctor end
  my_allocator::allocate     4 byte
  my_allocator::deallocate   0 byte
  my_allocator::allocate     8 byte
  my_allocator::deallocate   4 byte
  my_allocator::allocate    16 byte
  my_allocator::deallocate   8 byte
  my_allocator::allocate    32 byte
  my_allocator::deallocate  16 byte
vector dtor starts
  my_allocator::deallocate  32 byte

===============================================
deque ctor start
  my_allocator::allocate    32 byte
  my_allocator::allocate    128 byte
deque ctor end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque dtor starts
  my_allocator::deallocate  128 byte
  my_allocator::deallocate  32 byte

===============================================
list ctor start
list ctor end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list dtor starts
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte

===============================================
map ctor start
map ctor end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map dtor starts
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte

EASTL results, no deque available
===============================================
my_string ctor start
my_string ctor end
my_string add 3 chars
  my_allocator::allocate     9 byte
my_string add a huge number of chars chars
  my_allocator::allocate    115 byte
  my_allocator::deallocate   9 byte
my_string copy
  my_allocator::allocate    115 byte
my_string copy on write test
my_string dtors start
  my_allocator::deallocate  115 byte
  my_allocator::deallocate  115 byte

===============================================
vector ctor start
vector ctor end
  my_allocator::allocate     4 byte
  my_allocator::allocate     8 byte
  my_allocator::deallocate   4 byte
  my_allocator::allocate    16 byte
  my_allocator::deallocate   8 byte
  my_allocator::allocate    32 byte
  my_allocator::deallocate  16 byte
vector dtor starts
  my_allocator::deallocate  32 byte

===============================================
list ctor start
list ctor end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list dtor starts
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte

===============================================
map ctor start
map ctor end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map dtor starts
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte

This is useful to get the details of the underlying allocations, but unfortunately tells us nothing about overhead and expected cache performance.

@Joe right, it's hard to address all your questions in one answer. I'm not sure what exactly you mean with "overhead" and moreover, compared to what? I thought by overhead you mean the memory consumption.

By "overhead" I meant more the size of an empty instances of the structures and all their associated iterators, and how the more complicated ones handle allocation - e.g. does std::list internally allocate more than one node at a time, or do I pay the base allocation cost for each node, etc?

@Joe you see that overhead with the code above, the allocation size per node, my list uses 12 bytes per node with a value size int of 4 bytes, so its 8 bytes overhead, my map uses 24 bytes per node with a value size of 8 bytes (float, int), so 16 bytes overhead per node, I added both classes to the code above.

@Joe VC 8's map and list actually do an allocation on declare! See the output. Good to know

@Joe just tested STLPort 5.2 on win (VC8), it does not an allocation on declare for map and list, but for deque. Overhead for list and map is the same, added a comparison chart.

The question isn't so much "Please do this comparison" as "where is a resource for this comparison" - I don't think SO is a good place to "maintain" it. Perhaps you should start throwing it up on a Google site or wiki or something.

@Joe well now its here :p I'm not very interested in moving it to another site, I was just interested in the results.

std::string does not do copy on write. CoW used to be an optimization, but as soon as multiple threads enter the picture it's beyond a pessimisation- it can slow the code by massive factors. It's so bad that the C++0x Standard actively bans it as an implementation strategy. Not just that, but the permissiveness of std::string with dishing out mutable iterators and character references mean that "write" for std::string entails almost every operation.
Short string optimization is about 6 characters, I believe, or something in that region. Ropes are not allowed- std::string must store contiguous memory for the c_str() function. Technically, you could maintain both a contiguous string and a rope in the same class, but nobody ever did it. Moreover, from what I know of ropes, making them thread-safe to manipulate would be incredibly slow- maybe as bad or worse than CoW.
No containers do memory allocation by being declared in modern STLs. Node-based containers like list and map used to do so but now they have an embedded end optimization and don't need it. It's common to perform an optimization called "swaptimization" where you swap with an empty container. Consider:
std::vector<std::string> MahFunction();
int main() {
    std::vector<std::string> MahVariable;
    MahFunction().swap(MahVariable);
}

Of course, in C++0x this is redundant, but in C++03 then when this was commonly used, if MahVariable allocates memory on declaration then it reduces the effectiveness. I know for a fact that this was used for faster reallocations of containers like vector in the MSVC9 STL which removed the need to copy the elements.
deque uses something referred to as an unrolled linked list. It's basically a list of arrays, usually fixed-size in-node. As such, for most uses, it retains the benefits of both data structures- contiguous access and amortized O(1) removal and being able to add to both front and back and better iterator invalidation than vector. deque can never be implemented by vector because of it's algorithmic complexity and iterator invalidation guarantees.
How much memory overhead is associated? Well, honestly, that's a bit of a worthless question to ask. The STL containers are designed to be efficient, and if you were to replicate their functionality, you'd either end up with something that performs worse or in the same spot again. By knowing their underlying data structures, you can know the memory overhead they use, give or take, and it'll only be more than that for a good reason, such as small string optimization.

"It's so bad that the C++0x Standard actively bans it as an implementation strategy." And they ban it because previous implementations used it, or tried to use it. You apparently live in a world where everyone is using the latest optimally-implemented STL all the time. This answer is not at all helpful.

I am also curious what properties of std::deque you think prevent a contiguous underlying storage - iterators are only valid after removals at the start/end, not in the middle nor after any inserts, which can easily be done with a vector. And using a circular buffer seems to meet all the algorithmic guarantees - amortized O(1) insert and delete at the ends, O(n) delete in the middle.

@Joe: I think that CoW has been noted to be a bad thing since the late 90s. There are string implementations that used it- notably CString- but that doesn't mean that std::strings of the time did. You don't have to be using the latest and greatest in STL implementations for that. http://msdn.microsoft.com/en-us/library/22a9t119.aspx says "If an element is inserted at the front, all references remain valid". Not sure how you intend on implementing that with a circular buffer, since you're going to need to resize when it gets full.

http://www.gotw.ca/publications/optimizations.htm. July 1999.

I'm certainly not going to defend COW as an implementation technique, but I am also not naive as to how often software continues to be implemented using poor techniques long after they are identified as poor. For example, Maik's test above reveals a modern stdlib that does allocate on declaration. Thanks for the pointer about deque reference validity. (To nitpick, a vector can meet all the guarantees about iterator invalidation and algorithmic complexity; that requirement is neither.) If anything, I see this as further need for a document like my question asks for.

@Joe: I admit, the map and list in his implementation don't seem to have embedded-end optimization. However, I'm pretty sure that optimized-end has only been widely known for a couple of years- far less time than how horrific CoW is.

The question isn't so much "Please do this comparison" as "where is a resource for this comparison"

If that's really your question (which is most assuredly not what you said in your actual question text, which ended in 4 questions, none of which were asking where you might find a resource), then the answer is simply:
There isn't one.
The majority of C++ programmers don't have to care that much about the overhead of standard library structures, cache performance of them (which is highly compiler dependent anyway), or that sort of thing. Not to mention, you usually don't get to pick your standard library implementation; you use what comes with your compiler. So even if it does some unpleasant things, the options for alternatives are limited.
There are of course programmers who do care about this sort of thing. But they all swore off using the standard library a long time ago.
So you have one group of programmers who simply don't care. And another group of programmers who would care if they were using it, but since they aren't using it, they don't care. Since nobody cares about it, there is no real information about this sort of thing. There are informal patches of information here and there (Effective C++ has a section on std::string implementations and the vast differences among them), but nothing comprehensive. And certainly nothing kept up-to-date.

Speculative answer. +1 for probably true, -1 for no way of proving it.

I've seen many very good and detailed comparisons in the past, but they're all outdated. Anything before the introduction of move is pretty much irrelevant nowadays.


text:
Why is OpenGL provided with latest GeForce drivers so extremely slow?
I'm writting a code in OpenGL and using two computers - an old and a new one.
On the old computer (which I use for debugging/creating implementation for the old GL) I have GeForce 5500 FX. Before windows reinstall on it, I had NVIDIA drivers with OpenGL 1.5. And everything worked perfectly. Games made quite good FPS, even with dozens or hundreds sprites.
However, after XP reinstall, I installed the drivers provided with my video card but it seems there's no OpenGL at all (mysterious 'GDI Generic' renderer). So I tried to download the newest NVidia drivers. After their installation I saw there's OpenGL 2.3 but when I runned my app it worked with extremely low FPS (about 0.25, I mean I had to wait four seconds for any app reaction) with only one sprite. And as I loaded smaller images, the FPS relatively increased, but on the new computer it's always (no matter how big and how many sprites) speed, so it must be the perfomance problem. Without any sprites, it seemed it worked normal, but game without graphics doesn't make any sense.
That's why I downloaded the oldest drivers for NVIDIA GeForce 5500 FX I found on the Nvidia site. But they're still providing OpenGL > 2.0 (2.1 exactly). The problem's the same.
I also tried to change all the properties of OpenGL to increase performance but it didn't help too.
So what can I do? I'd like to find drivers with OpenGL 1.5 but it seems they're not on the NVIDIA site and most people say it's the best to download they from there.

Is this an application you are developing, or you downloaded?  If it's one you made, what framework are you using for the OpenGL interface?

Yes, it's written by me. This is actually framework for 2d games that uses OpenGL and SDL.
(I mean what I'm writting is a framework)

Just curious, I'm writing an SDL application right now as well.  Are you using any OpenGL extensions in your application, or is it strictly textured (obviously with a few vertices)?

I'm not sure. Are you asking about something like VBO? If yes, I'm not using such things. I just use textured quads to display loaded images.

Just curious, have you changed any parts of the code pertaining to OpenGL features (e.g. added any glEnable calls, or used any GLextensions) which may have raised the OpenGL base version?  It might be worth trying a binary from before you formatted (if possible).

Mhm, I added glEnable whenever I'm drawing an image, but it worked before. I have the old binaries which worked fast on the old computer before. It's slow now but not on the new computer. I also use multisampling but even when I turn them off it's still slow.

The Super User version of your question was migrated back to GameDev because the problem seems to be more about how you are writing code, than about how the drivers are set up. I recommend editing it to make it more clear what you have done, and also please do not cross-post.

You know there is no OpenGL 2.3, do you?

The problem is most likely that you're using non-power-of-two textures.  The drivers for the GeForce FX series support these texture sizes, but will force your program to run in software mode.  If this is the case then you'll need to use power-of-2 texture sizes (2, 4, 8, 16, 32, 64, etc) instead.

It sounds like the 2nd machine is doing software rendering - hence the slow frame rate.
I'd check that the new version of OpenGL is detecting the card properly. It could be that it thinks that it doesn't support OpenGL fully - or at least the bits you are using - hence the fall back to software.
Do other applications that use OpenGL work OK?
If it's just your program it could be the way you are initialising OpenGL. I'd post a question on Stack Overflow - with the code.

You're right, one of the games (Commandos) using OGL works properly. In "OpenGL Extensions" application I can see detected video card - GeForce FX 5500/AGP/SSE/3DNOW!. So does it mean that it's not using software rendering? Or I should check it in a different way?

@somnock - it sounds like your application isn't initialising OGL correctly. Been a while since I did any of this so I can't offer concrete advice. Post your code on Stack Overflow or try creating a new application and see if that works.

Nvidia have an entire archive of all their older driver versions that you can find at their Windows XP/2000 Driver Archive
Specifically this version (71.84) Claims to have OpenGL v1.5 so if you want to give it a shot with an older version to see if that truly is the problem then there is nothing actually stopping you.

Okay, but will they work with the 5500 FX version?
I'm asking, because when use this old/beta drivers finder (with windows xp) it seems to not detect version mentioned by you.

The Release Notes do list the FX 5500 as being supported, page 24 if you're interested. Seems that above version 80 you get OpenGL V2.


text:
How can I draw beautiful lines with XNA on WP7?
I'm trying to figure out how to draw good looking lines using XNA on the WP7 platform. By good looking I mean something not skinny and flat that a simple primitive gives you. A nice gradient, or texture or something applied.
It would be pretty easy if the lines were all straight, but I need to be able to make 45* and 90* turns.
Has anyone else tried doing this? I have found ways to do it, but they all require custom shaders which the platform doesn't support. Like this one for example
Example output from that library:

What the vertex shader for the round-line library that you linked does is simply take your two positions and use those to transform a pre-calculated outline of a line (including appropriate stretching).
You could do simply do the same transformations on the CPU, using DrawUserPrimitives or a DynamicVertexBuffer to draw them via BasicEffect.
You could then also calculate appropriate texture-coordinates on the CPU, to apply a texture of your choice (or use vertex colours for a gradient, and so on).
For a small number of lines, this should be perfectly acceptable, performance-wise.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Walkin on terrain - Opengl
i wanna walk to terrain...
first i created the terrain
void desenha_terreno(float px, float pz){

for (int z = 0; z < iwidth-1; z++)
{
    glBegin(GL_TRIANGLE_STRIP);

    for (int x = 0; x < iheight-1; x++)
    {
        // for each vertex, we calculate the grayscale shade color,
        // we set the texture coordinate, and we draw the vertex.
        /*
           the vertices are drawn in this order:

           0  ---> 1
                  /
                /
             |/
           2  ---> 3
        */

        // draw vertex 0
        glColor3f(terreno[x][z][1]/255.0f, terreno[x][z][1]/255.0f, terreno[x][z][1]/255.0f);
        glTexCoord2f(0.0f, 0.0f);
        glVertex3f(terreno[x][z][0], terreno[x][z][1], terreno[x][z][2]);

        // draw vertex 1
        glTexCoord2f(1.0f, 0.0f);
        glColor3f(terreno[x+1][z][1]/255.0f, terreno[x+1][z][1]/255.0f, terreno[x+1][z][1]/255.0f);
        glVertex3f(terreno[x+1][z][0], terreno[x+1][z][1], terreno[x+1][z][2]);

        // draw vertex 2
        glTexCoord2f(0.0f, 1.0f);
        glColor3f(terreno[x][z+1][1]/255.0f, terreno[x][z+1][1]/255.0f, terreno[x][z+1][1]/255.0f);
        glVertex3f(terreno[x][z+1][0], terreno[x][z+1][1], terreno[x][z+1][2]);

        // draw vertex 3
        glColor3f(terreno[x+1][z+1][1]/255.0f, terreno[x+1][z+1][1]/255.0f, terreno[x+1][z+1][1]/255.0f);
        glTexCoord2f(1.0f, 1.0f);
        glVertex3f(terreno[x+1][z+1][0], terreno[x+1][z+1][1], terreno[x+1][z+1][2]);

    }
    glEnd();
}
}

I can move the camera with the functions:
void keyboard (unsigned char key, int x, int y) {
if (key=='w')
{
    float xrotrad, yrotrad;
    yrotrad = (yrot / 180 * 3.141592654f);
    xrotrad = (xrot / 180 * 3.141592654f);
    xpos += float(sin(yrotrad))*5;
    zpos -= float(cos(yrotrad))*5;
    ypos -= float(sin(xrotrad))*5;

}

if (key=='s')
{
    float xrotrad, yrotrad;
    yrotrad = (yrot / 180 * 3.141592654f);
    xrotrad = (xrot / 180 * 3.141592654f);
    xpos -= float(sin(yrotrad))*5;
    zpos += float(cos(yrotrad))*5;
    ypos += float(sin(xrotrad))*5;
}

if (key=='d')
{
    float yrotrad;
    yrotrad = (yrot / 180 * 3.141592654f);
    xpos += float(cos(yrotrad))*5;
    zpos += float(sin(yrotrad))*5;
}

if (key=='a')
{
    float yrotrad;
    yrotrad = (yrot / 180 * 3.141592654f);
    xpos -= float(cos(yrotrad))*5;
    zpos -= float(sin(yrotrad))*5;
}

if (key=='q')
{
    yrot += (float) -0.5*5;    //set the xrot to yrot with the addition of the difference in the x position
}

if (key=='e')
{
    yrot += (float) 0.5*5;    //set the xrot to yrot with the addition of the difference in the x position
}

if (key=='r')
{
    xrot += (float) -0.5*5;    //set the xrot to yrot with the addition of the difference in the x position
}

if (key=='f')
{
    xrot += (float) 0.5*5;    //set the xrot to yrot with the addition of the difference in the x position
}

if (key==27)
{
    exit(0);
}

glutPostRedisplay();
`

and, i change the position with the values of x,y,z positions
    // clear screen and depth buffer
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
glLoadIdentity();

//glTranslatef(0.0f, 0.0f, -cRadius);
glRotatef(xrot,1.0,0.0,0.0);
glRotatef(yrot,0.0,1.0,0.0);  //rotate our camera on the    y-axis (up and down)

glTranslated(-xpos,-ypos,-zpos); //translate the screen to the position of our camera

// set the camera position
//gluLookAt(cameraX, cameraY, cameraZ, lookX, lookY, lookZ, 0.0, 1.0, 0.0);

// set the current texture to the land texture
//glBindTexture(GL_TEXTURE_2D, land);

    desenha_terreno(xpos,ypos);
    glEnable(GL_BLEND);

// enable read-only depth buffer
glDepthMask(GL_FALSE);

// set the blend function to what we use for transparency
glBlendFunc(GL_SRC_ALPHA, GL_ONE);

// set back to normal depth buffer mode (writable)
glDepthMask(GL_TRUE);

// disable blending
glDisable(GL_BLEND);

    glFlush();

    glutSwapBuffers();

    angle++; //increase the angle
   }

well... i need to walk to the terrain, above the terrain, help me please!

Jeez, wall of code much? What have you tried? What do you know about what you're trying to accomplish?

Are you talking about simulating walking on terrain as if the player is the camera?  It isn't difficult to adjust your Z value as you move by simply querying your terrain and getting a height to which you'd apply your offset to.  http://books.google.com/books?id=kwQuwDmfthwC&pg=PA228&lpg=PA228&dq=walking+on+terrain+3d+game&source=bl&ots=LbdhoAWfzy&sig=70IK8q3EDvCwUGmYZDVwIOLBYj4&hl=en&ei=ikrpTdaADOLZ0QHqv52RAQ&sa=X&oi=book_result&ct=result&resnum=4&ved=0CDYQ6AEwAw#v=onepage&q=walking%20on%20terrain%203d%20game&f=false

yes, simulating walking as a player... thanks Robb, i will see the link!

Honestly, who upvotes such questions?

The answer is very simple.
When you render terrain you supply 3 values, x,y,z. Lets assume that z value is height. So when walking you just need to keep camera above z value! You get camera x,y query height in that spot and place camera above z value.When there is no z value for this spot interpolate from near by points.
Thats all.
You also may want to keep camera some constant above terrain itself (to give illusion of being physical character).
You also may want to put all height in one array. And assume that x and y change by const interval, to simplify your terrain generation. And you get height-map!

You may have some luck with using gluLookAt() to manipulate the camera. It'd probably be easier to move the camera position and the point that it's looking at instead of rotating the camera yourself. This would also simplify doing things like "looking around" from a stationary point.

The best way to make sure you're above a triangle is to use barycentric coordinates.  In short, this is a coordinate system local to a triangle that allows you to get the height of a point somewhere in the interior of the triangle.
So your algorithm would go something like:

Get the camera/player position
Figure out what triangle that player is on (assuming you have a regular grid of triangles in the (x,y) plane this should be trivial).
Using the 3 points of that triangle convert the camera point to triangle space and use the barycentric coordinates to solve for the height.
Unproject it from triangle space back to world space and you'll have the point on the triangle where the camera should be.  You'll probably want to move this up so that it appears the camera is on the terrain proper.


text:
Detecting a sequence of nodes in a grid
Given the image below, I need to detect the most optimal sequence on the board (the green line). The blue/red lines represent possible, but not the best moves.
Here are the rules:

You can move to any tile that is the same, and is your neighbor (diagonal is valid)
Once you have visited a tile, you can't visit it again.

I have thought about looping through each node, and looking at its neighbors, then recursively going through. Once I find a possible move I can put it into a structure. Once all possible moves are found I just pick the move with the highest count of node. It becomes more difficult when a node has more than one neighbor that matches.
So, is there some algorithm that I can use? I was thinking some sort of flood fill, but that doesn't meet rules #2.
As requested, here is a video of similar gameplay. http://youtube.com/watch?v=eumnCTG0AE8

It might be important to note that the 3 swords/gold are possible matches, but I just didn't include them in the image.

Why are the 3 swords/gold possible matches? Do you want to find all paths that consist of at least 3 items?

yeah, that is the idea.

You can consider each group of linked identical symbols (and by linked I mean you can travel from one symbol to another) a separate graph. For each such graph apply a Depth First Search (DFS) starting from each node in the graph that isn't already part of the longest path for that graph. Every time you reach a dead end while applying a DFS, check to see if the path you've just traversed is longer than the global maximum that you've found so far. If it is, store it as the new longest path.
You'll notice that in the previous paragraph I mentioned applying a DFS multiple times for each graph. A single DFS ran on a graph wouldn't be enough. Consider this particular case:
    1
1 1 1
    1
    1
    1
    1

If by chance you would first run a DFS on this graph in the topmost node, you would discover the longest possible path as being the vertical line, but that wouldn't be correct. This would happen every time you start the DFS algorithm in a node that's somewhere inside the resulting path or is not part of it at all. What you need to do in this particular example is also start  a DFS algorithm from the left-most node in the second line. That will find the correct path. Generally speaking, you'll need to run DFS algorithms in each node that isn't currently part of the longest path for that graph, as stated above.
The absolute worse case scenario for this algorithm would be a board filled or mostly filled with a single symbol type, however that's unlikely to happen in the game. Also, be careful how you store the longest paths for each graph. If you don't optimize this bit, you might be better off just calling a DFS for each node on the stage. Assuming that you don't work with very large boards and that speed isn't that big of an issue, this solution should be fast enough.
Technically speaking, by breaking down your board into separate graphs you end up with multiple "Longest path problem"s. As we can see from your example, you can have cycles in your graph (for example, having all of the symbols on the outside of the stage of the same type), which means that in this particular problem you need to find the longest path in several cyclic undirected graphs, which can't be done in polynomial time.
If you find that this is too slow, see this answer on StackOverflow for more details on how to optimize the individual "Longest Path Problems".


text:
C# Game Setting message Takes away first character
So If you set it to like

abcdefg

it will come out like

bcdefg

Here's changing the message

Here's the result

Here's the code
//Set Welcome msg
else if (Type == 6)
{
    if (Character.Network.Stall.isOpened) return;
    short length = Reader.Int16();
    Character.Network.Stall.WelcomeMsg = Reader.Text3();
    Character.Network.Stall.Send(Packet.StallWelcome(Character.Network.Stall.WelcomeMsg));
}

Any help?

Your question lacks a lot of context. What is the Character class? What is "Game Setting"?

The images load fine for me.  You may need to post additional code in order for the truncation to be diagnosed properly.

Oh hey look it's Silkroad Online.  It's cool to see this kind of thing on StackOverflow!

char is 16 bits, are you sure you aren't reading the first char when you try to read the length?
Try reading the whole block as text:
else if (Type == 6)
{
    if (Character.Network.Stall.isOpened) return;
    Character.Network.Stall.WelcomeMsg = Reader.Text3();
    Character.Network.Stall.Send(Packet.StallWelcome(Character.Network.Stall.WelcomeMsg));
}


text:
Network Message Format Specification
I'm working on a TCP turn multiplayer game.
I've read many tutorials and stuff, and they all said to use Async IO, but, none of than give practical examples on how to do it.
I was thinking that in every TCP data stream sent, the client would have to send who is he, and what he's doing. Is it really necessary? What's the best way to deal with host identifying? If I should deal with this at all...
Should I check in every message if he's who he's claiming to be?
There's any comprehensive game packet analysis avaiable on the web? I think I would learn much from this kind of source.
EDIT: I'm doing a server/many-clients model.
Thanks,
Julio Rodrigues

"Should I check in every message if he's who he's claiming to be?" - There's no real way to do that, any method you use can be circumvented by an able hacker. You can only make it harder.

Let me try answering that from positions of RTS (think of it as TBS where each turn is 100msec).
There is separate thread for receiving and sending messages, it has it's own buffer and is black-box to the rest of the game (the game should know nothing about protocol and format). The game sends commands to networking unit and receives complete commands as they are available and verified to be complete.
When networking unit receives a new message it appends it to buffer and checks if buffer has a complete command. That is why each message has a header specifying contents length and CRC. That is ASync part of it.
How to identify the host? That depends on your network layout, is peer-to-peer or centralized server or .. ? If you trust your clients to do the computations (not advised for serious gaming) then there's no host at all, Everyone trusts everyone to supply valid data. If you have a separate host (could be running as stand-alone task on one of players machines) - it does all the computations and clients act as terminals, doing only View-Controller roles.
EDIT:
We use TCP module from OverbyteICS (that is one more layer between the networking module and Net) and it does it for us, each time new connection is made it is assigned new "stream". So when message arrives we know the "stream" who sent it, but in networking module we keep remap table, so that in lobby all players have UIDs and in game all players are IDs 1..8 (again, game knows nothing about networking UIDs).
As for specific details I can't say how it's made inside OverbyteICS, but we have possibility to launch local server and 1-8 clients on the same PC (all having same IP 127.0.0.1) and they are all distinct in game, so this means OverbyteICS takes care of that.

+1 "the game should know nothing about protocol and format"

The thing is, with Async IO, and with players with the same IP I need to have a way to uniquely indentify them, right? I was reading that I need to make a Game Network Protcol, even a if it's simple one, does this make sense to you?

Thank you for the explanations, I'm doing something like this.

This isn't necessarily an answer, but whenever I have network architecture questions, I refer to this wonderful document about how Unreal Engine does it:
http://udn.epicgames.com/Three/NetworkingOverview.html
It's way more than you need, but it's a great read and you'll likely be able to use concepts from it.

I'm reading it, seems to be very useful!

Async IO is just a general term for handling input and output. How to actually implement that depends entirely on the platform and language you're using. Usually the result is that you just set up a connection and then you have callbacks which get called when data arrives on the connection.

I was thinking that in every TCP data stream sent, the client would have to send who is he, and what he's doing. Is it really necessary?

No, it's not necessary. TCP is a connection based protocol, between 2 end-points. For as long as the connection is up, you know it's the same person on the other end, so they only need to identify themselves once.

What's the best way to deal with host identifying?

You can get the host's IP address and port from the network API you use, when connected. Again, how to do this depends on the API. A remote IP address and port pair is a unique identifier for incoming TCP connections.


text:
Is Tetris public domain?
is the concept for Tetris in the public domain or is there someone who is still collecting royalties on the concept? I mean, if I were to write a variant of Tetris would I owe somebody some money?
Thanks.

Very interesting question! I'd imagine the answer is yes if it has ever been copyrighted, but I see clones of it all the time...

Here's a nice blog that covers the legality of Tetris: http://desiree47.wordpress.com/

Interesting blog post, but in the comments, someone mentions a reject app (App Store) because of "resemblance to a well-known third-party trademark, Tetris".

The game, name, and all associated works of Tetris are owned and trademarked by The Tetris Company.
The concept of tetrominos, however, are not owned by anyone. Though The Tetris Company's website indicates the term 'Tetriminos' is in fact trademarked.
Whether you can create a clone of Tetris under another name is certainly up for debate. Recently a 'Tetris-clone' named Blockles was removed after litigation from the Tetris Company was brought against it. I have not been able to find the game in question to see just how close to the original Tetris game it was.

Is there a description of the copyright "The Tetris Company" holds on the Tetris gameplay itself? (not on the name...) Does any game made up of falling tetrominos automatically infringe the patent?

Tetris has been programmed in 1984 and sold commercially ever since.
Since his author is not dead yet (I think), and certainly not dead for 70 years, it's definitely not in the public domain.
It's not an abandon-ware either because there's at least one company that claims to have the rights and wants to make money out of it.
Now, as to who really owns the rights, that's highly questionable, as you can see in the Wikipedia article.

Алексей Пажитнов is alive and well, last I checked. :)