text:
Sharp DX Identity Matrix, Matrix.Forward vector pointing at negative Z
I'm trying to take a steady grip on Sharp DX. Already done some work like translating, scaling and rotating objects. Now i have to calculate the rotation matrix using only direction vector and arbitrary UP vector which is Unit Y vector (0,1,0). And this is where everything I know about Direct X graphics falls apart: I filled the Matrix.Forward with the normalized DIRECTION vector, and then crossed it with arbitrary UP (exactly this: DIR cross UP, not the other way), the resulting vector put in Matrix.Right property. Now if I put (0,1,0) in the Matrix.Up property, my model is facing the exact opposite direction to the expected direction (it faces backwards). Further investigation brought me to the fact that the Matrix.Identity matrix faces the NEGATIVE Z direction, which is weird to me as I thought that Identity would face positive X,Y,Z axes. Now I can overcome my problems by flipping any of the axes, but this clearly is not comforting to me, as there is something i must have missed in the meantime. So the ultimate question is: Why my Identity matrix points positive Y axis (good), positive X axis (nice, i expect this) and NEGATIVE Z (help!)

A cross product gives you the perpendicular line. Both the negative and the positive vector represent the same perpendicular line. You'll have to change your order of operations to get the positive vector. Eg. DIR cross UP and UP cross DIR will give the same perpendicular line but might change the sign of the vector. (It's too early to do matrix computations to show that :P)

Thank you for the quick answer. Of course I can arbitrarily change the order of operations, or arbitrarily flip my axes to achieve the desired effect. The problem is: My arbitrary calculations DO work but I don't know WHY they work, which makes me feel like i'm loosing control over all of this. If i change the order of operations, I have to change my FORWARD vector to the opposite-facing vector, and I don't feel very comfortable with such hacks. Also: the Identity matrix has -1 Z in its .Forward component. Why so? :( SharpDX uses left-handed system, just like DX

Well you can always just do a cross product on paper to see what happens, the order of operations is important and it will matter.


text:
Is it feasible for a Server to send nothing more than a tile-based area to a Client?
To start, I have a good amount of background in networking (hardware, routers, ex.) but very little knowledge past the basics of network programming. This may seem like a stupid question, but I want to know what I am getting myself into while fathoming the implementation of multiplayer in my game.
I am creating a tile-based world, which is generated through a simple 2D Array. Let's say something like World[100][100], for simplicity's sake.
Currently, the render method only renders the tiles based on the resolution of the window, plus one tile (for smooth rendering during movement.) No matter how large the world is, (10x10, 1million x 1million) the rendering is flawless in performance.
The gameplay needs nothing more than to know what is in the currently visible (rendered on screen +1) and at the most possibly SOME information of tiles in an area around the player.
So anything more sent by the Server wouldn't be the full tile information.
Ex. Items laying on the ground, ground type, trees, etc. would not be important in the area outside the player's view, but would only be what the Client/Player needs to know about in those tiles. (Ex. Ultima Online's 'incoming names' where players could know a Character [player or monster] was just beyond the tiles in their rendered view.)
I do not know very much about networking, so perhaps as I learn this might answer my question. However, I am curious if this is a feasible solution or if the idea is simply laughable.
The information being sent would be about a 10x15 area of tiles, and each tile holds information about what is on the tile.
More efficiently, everything would be an Object, where the tile holds all the Objects on the tile. Ex. Tile[4][4] holds Sword#23452, Rock2, Tree5, Player3, Monster4.
Empty tiles would send nothing more than terrain type [Grass, Sand, Water] if not already loaded during Initialization/Load. Some tiles would have a handful of objects [Tree2, Sword#924, Gold, Corpse, Rock3].
So I cannot imagine that a tile would have very much information to send to the Client from the Server, since the Client mainly only needs to know the Texture that needs to be loaded and Position to place it on screen. Position being only two integers and Texture being one integer for a list of files to tell the client to render.
At the craziest, the Server would have to send 150 tiles with information of only a handful of Objects OnLOAD, and from then on update only changes to tiles (if any) and any new tiles (10 to 15 everytime a player moves in a direction) and the direction of movement for characters on screen (so the client can simulate smooth movement between tiles).
I assume I am correct in thinking this is an incredibly low amount of information being sent over the internet or between peers, so it should have little problems with performance even over laggy connections? Or am I so ignorant of networking that my mind will be blown when I finally get around to opening up my book on multiplayer networking?
If it is a very low amount of information being sent between Client/Server, would it make more sense to simply load the entire World on Initialization? Or 'Map' if the World is excessively large. And then after LOAD, send only tiles which are updated?
I am still pondering how I should specifically deal with data. The book I am using as reference wants me to have a Linked List, where I add and remove objects, so everything is a bool. "Is there a Character? Is there a Tree?"
I was thinking of a different approach, such as a container which holds objects, and Server logic that sends only what is required to tell the Client what to render. Possibly with objects that hold networking information within itself, which is sent out when called for by the Server.

I suggest you take a look at freemmorpgmaker.com, this engine helped me a lot when I just started out. The script is relatively simple and a lót of fun to work with. The code taught me everything I needed to know to create my own 2D engine/game. What you should not learn from them is how to secure your server/client.

You are on the right track.
Consider Minecraft.  Minecraft only loads the areas (also called chunks) immediately surrounding players.  This is how the server is able to run without running out of memory, and why clients don't get bogged down from network traffic.

If it is a very low amount of information being sent between Client/Server, would it make more sense to simply load the entire World on Initialization? Or 'Map' if the World is excessively large. And then after LOAD, send only tiles which are updated?

This is exactly what you should do.  Only send the data that you need to send.

When a client joins, send it a chunk of the tile map (or all if it, if you're dealing with small areas)
When the player tries to modify a tile, send that data to the server.
When a tile changes state, send a packet with that information to all relevant clients.

If you're just sending a 2D array of tile IDS, the size of the data can be very low, especially if you have less than 256 different tile types.  In that case, you could use a single byte (or unsigned char).  So if you're sending 100x100 tiles to the player, and each tile only consists of a single byte... You get the idea.  It is not a lot of data.
The Minecraft community has done a wonderful job documenting its protocol:
http://mc.kev009.com/Protocol
http://www.minecraftwiki.net/wiki/Classic_server_protocol

wow, thank you very much!
This is a big confidence boost that I was told I am on the right track, when I know so little. It tells me that I am understanding things correctly and engineering to the best that I can. I am confident that if I keep learning, I will do adequately enough.
It is so satisfactory to hear positive advice, and no "You are doing it wrong!" lol :)

It took me a long time before I gathered the nerve to take multiplayer and 3D games.  :)

Also, positive advice is what this community thrives on.  I encourage everybody to contribute in any way they can!

It is generally a good idea to only send the information to the client which is supposed to be shown to the player. Following this principle reduces network traffic and prevents cheating.
But keep in mind that when the player moves their character, you certainly want to start the move on the client-side before receiving the confirmation from the server to make the game appear less laggy and more responsive. That will likely mean that you also want to start scrolling the screen to an area which isn't loaded yet. This forces you to leave this part of the map blank and replace it with the actual world when it has loaded. That would be quite an immersion-breaker. For that reason you should preload the area in a certain radius around the players screen.
The size of the preloaded area depends on how fast your players can move and how long their average latency will be.

The amount of data you are sending from the Server to the Client can be INCREDIBLY insignificant. If this is all you need to send, I would vehemently suggest loading as much as you can on Load, so it is even less data required. The amount sent on load will be small enough to justify the load time, the memory usage will be nearly non-existent unless your world is ridiculously oversized, and you will need to update almost no data at all.
I imagine you could also do some neat tricks to optimize lag prediction which compensates for the average delay a user experiences, allowing for predictable movement with characters.
Also prioritizing the insignificant data with Character movement and Character actions/reactions being highest in priority can help to make sure even laggy players feel very little lag.

source: Stack Exchange

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

sort: votes


text:
I am looking for a word to classify Game Objects (Trees, Rocks, even Bridges) but NOT include Items/Characters
I am looking for a SPECIFIC definition that includes environmental game objects but NOT other game objects. Trees, Rocks, or even Bridges. NOT items, NOT weapons, NOT Characters, NOT tiles. I'm looking for an answer that is extremely specific for certain entities but NOT most entities.
For my GameObjects, I have them stored as an ObjectType.
typedef enum
{
CHARACTER = 0,   //A PC or NPC
ENVIRONMENT = 1, //A tree, a Rock, a Bridge, a non-animate environmental object
ITEM = 2,        //A sword, bag of gold, pickup-able item
} ObjectType

Obviously, anyone would easily understand that a Character GameObject would be a Character (PC or NPC), and an item would be something like a Sword, bag of Gold, etc.
However, the word "environment" is obviously wrong. I thought of "foliage" to refer to any object that isn't a tile (grass, road, water, a floor) and isn't an item (can pickup, etc.)
Normally, I would call these things 'Objects', because a Tree, a Rock, a Bridge, a Bush, a collection of flowers- these are all objects. However, this is redundantly confusing when GameObjects are referred to as "Objects" and the term 'object' is so common in game engineering.
I couldn't help but think to myself, "There must be a term that is obvious, that I am just not seeing. A word that describes this very common type of game object."
Something that people could easily understand, so I don't have to resort to "EnvironmentObject".

Every engine/company has their own way of doing it, and you're going to get 20 different more or less equally "correct" answers.  The most generic is the exact term you used: game object.

Game Object isn't an answer at all. In fact, that would be an INCORRECT answer. GameObject is the name for the Game's Objects. A categorization for each object is what I'm looking for: Character, Item, Tree, Doodad, Prop.
I cannot believe someone with 11k rep would provide the only incorrect answer, thinking it's a correct one.

Who is the audience for this word?  Why do you need the distinction?  Is it for the name of a class?  In a component-based engine, an environment object might not be anything more than just a game object that renders the kind of prop.  Is it for artists to sort out the environment objects from other kinds of objects?

In the traditional world of simulations this fluff in the environment is called "culture."  This idea comes from stuff encompassing artificial, "cultural" objects like roads and buildings.

Related question: http://gamedev.stackexchange.com/questions/47746/dictionary-of-common-names-for-code-objects?lq=1

Something which is part of the set is a "fixture", or "landscaping".

Hi Anon! This is a bit brief - I think you should consider leaving this as a comment or editing your answer to contain a bit more information.

Chosen as best answer, because honestly this IS the best answer. I wanted a definition that could encapsulate environmental objects such as Trees, Rocks, or even Bridges... but NOT items, weapons, bags of gold, etc. "LANDSCAPE" is the absolute best answer.

"LANDSCAPE" is the best answer because an Item is NOT a landscape. A character is NOT a landscape. A Tree however? Definitely. A rock? Definitely? A bridge? Could definitely be. This is the most specific answer, the only one that correctly answers the question, and the only person who read it correctly (although others DID provide great answers- but their answers could easily include Items, Weapons, and other props).

I believe Prop ( See: http://en.wikipedia.org/wiki/Theatrical_property and  https://developer.valvesoftware.com/wiki/Prop_Types_Overview ) is commonly used. There are less ambiguous alternatives, for example Blizzard uses the word Doodad.

Almost chosen as best answer. I used this for Items + Environment landscapes. I've always called them Props in Unity (i forget why), it makes the most sense when designing scenes, fits in anything that isn't a character, and is very generic but understandably detailed! :)

This is it. I always call them, and seen them called "props".

I would use the word Doodad for those environmental things as it's a standard. When editing in both Titan Quest and StarCraft's Map Editor, they're referred to as Doodads.
http://starcraft.wikia.com/wiki/Galaxy_Map_Editor#Terrain
I usually refer to objects an Actor can interact with as Props, just as if they were on a stage. Actors use Props to do actions, whereas the Doodads only complement the scene.

"Decoration" has always been the name I've given to non-interactive, non-collidable elements.
When using flixel I would have level data defined by three separate layers Solid, Interactive and Decoration.  Solid and Decoration would then be loaded into Tilemaps, both would be rendered but collision checks would only be made against Solid.

Great answer, thank you. +1
I really like this answer too. Almost chosen as best answer.

Just to let you know, this is definitely the 2nd best answer. It helps me answer a similar question I would have later when my game gets more detailed. I will be calling Trees, Rocks, Bridges, "LANDSCAPE" while calling fixtures such as torches, furniture, "DECORATION". The LANDSCAPE will most likely be transformable (chop down a tree, bust a rock) while Decoration is closer to an item but with absolutely no information besides graphical representation.

Like Hatberg said I used to hear them called "Props" when I was younger but after I took a few game development classes in college (ironically taught by the founder for Iron Lore Entertainment (Brian Sullivan) who made/designed Titan Quest) I heard purely decorative game objects being called "Set Dressing". I guess it's just a synonym for Prop but I find most people prefer Set Dressing now a days.

Sounds like a salad or food object, not a game object, lol :P

what's wrong with salad? But yeah I actually thought it was a bit weird when I first heard of it too. I really only go used to it because I heard so many people use the phrase as well.

You could call them Entities and give them an Environment tag as an enum. You could also go with a component based design and just attach a "Render" component so that all that happens to these environments is they sit there and look pretty.
Calling Trees and environments Entities may not sit well with people, but to me it makes sense to call them "entities" of the scene. It allows you to eliminate the need for more classes and thus making it more simplified to understand as long as you document your design.
Edit1:
My original answer is trash and was a result of not properly reading the question. As other better answers have already mentioned, you can tag these items are 'props' 'Doodads' or even 'Decorations'.
Just for this answer I hoped to provide you with yet another word after looking at the Doom3 source code. I have ripped through it looking for how they tag their "Entities" or "GameObjects as you have decided to call them. From what I can see they do not have an obvious tag for it. They seem to just build an IdEntity and give it a RenderEntity which has the data for the renderer to render. They also have a Model class, but no obvious Environment Tags that I can see. I will edit this answer if I end up finding anything that is close to an "environment" tag.
Edit2:
It looks like doom classic straight up built classes for "Wall" "Floor"(also functioned as ceiling) "Things" and even "sky". So I guess "Thing" could be used, although that seems vague. I guess it is similar to doodad.

I figured Entity would be a better name than "GameObject". When I said environment tag I was being entirely too general and I definitely was not answering the question, considering your question was more focused on identifying a word for the tag itself. Obviously, I failed to really read and think about the question fully. It was more specific than I originally thought. I apologize. I believe others have done a great job answering the question but I can try editing my answer so it is not dead wrong in case others read it down the line. Thanks for bringing this to my attention.

@Regeta I edited it. I am still looking through Doom3 Source to see if they may have a fancy name for their Environment tag. Not having much luck so far.

+1 for improving the website and being humble enough to self-review and admit not reading it fully. Other users on here didn't really read it either, and a moderator had to step in and reverse FIVE high rep user's errorenous opinion, and one in particular tried to troll in comments that he wasn't wrong and a huge paragraph as to why. @Dean Knight thank you for being a shining example of the type of person this community needs. Your humility and self-respect is something I wish upon all the high rep users who abuse their voting privileges.

@Regeta SO has done nothing but help me. I enjoy trying to spread what little bit of knowledge I can. Thanks for being fair.

Terrain works.  You could also divide it into Terrain_water and Terrain_land

Hey Thomas, welcome to the site. Questions like the above are subjective questions that require a bit more fleshed out answers. The see this help page at the bottom it talks about these types of questions and how they should be answered.

What about the word "Scenery"?

You should try to add more to your answer, especially since this question has already been answered.

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


text:
Do associative array data structures have a place in game development?
Is it a bad idea to use a map data structure (an associative array or dictionary) in game development?
According to this flowchart, the ideal container for storing game object's container would actually be a map for many games. But I've heard anecdotal claims that maps are a very bad choice for games.

Is this true?

It depends on the map container implementation really.. But for example, a std::map from the c++ STL has many uses and one just cant predict it will be inappropriate in every situation. There are always places it can be used without any concerns and may actually be a great tool for the job..

Alright, well to be specific, let's say the container will hold all of the game's GameObjects. Everything that can be rendered or needs data, as its own "Game Object". Is a map still "horrendous"? The answer I am referring to is from a high rep user who said that you should ALWAYS (emphasized) use an Array or Vector, and that a Map or Linked List is "horrendous" for game design, period. Are you saying he is wrong?

I dont think that you need to find gameobject by key. Depending on a game, some game mechanics might require you to find a specific game object in some way. But thats not a problem of something that holds all game objects.

associative containers are great for many things. probably not the most fit for your particular example. Whenever you have many objects and need fast iteration, its awesome to have an array or vector instead. Contiguous data in memory is very important because of cache-misses and so on. As long as you know your associative container very well, you can obtain performance gains from it you could never with arrays.

Yeah, I could imagine storing a player_Trigger box, and the prop_Door that it opens as "pt1_door_trigger" and "pt1_door", but I wouldn't see that logic for various background objects like trees or rocks. I will say that when I interviewed at an MMO company, they tended to use numerical IDs for players/game objects, associated using a map, so that they could very easily handle objects suddenly not existing.

I worked on a 2.5D game where all the rendered objects were stored in a multi-map with their z-position as their key, because there was no depth-testing and it was very important they be rendered in order, back to front. Maybe not the perfect solution but I wouldn't call it horrendous.

@Eric Hm...I get how that helps their rendering, but that still doesn't fit the use case of a map. You'd never be coding and think "I need to find the object drawn at Z-index 247; and only that one". Usually, you'd just be looping through all of them sequentially, and other data structures tend to be better for that. In that case, something to the effect of an array or vector might be better - but I'm afraid I don't immediately know which. (You could have a map in addition, to get the specific object you need for game logic though)

@Katana314 a few objects were constantly moving, such as the player and monsters, while most objects were static. The non-static objects could be removed and inserted and the sorted order would be maintained by the map, instead of having to manually sort a vector or array every time anything moved. Indexing by position was not the advantage of the map, maintaining sorted order was. Strictly speaking it was actually a multi set, not a multi map, and the objects had an overloaded comparison operator, but whatever.

Are associative arrays a good idea for games? Perhaps, depending on your needs.
However, you need to differentiate between comments about "associative arrays" and specifically about the class std::map.
Associative Arrays
Associative arrays are just some kind of data structure that allows you to associate one kind of value with another, such that you can look up a value with another value. There are many kinds of associative arrays, some of which are really implemented with a regular array.
Hash tables are a form of associative array.
The "conventional wisdom" among many C-style game developers is that looking up entities by name is not worth it. This "wisdom" effectively says that your entities should be in one big global fixed-size array. When you create a new one, you find an unused index, set it to be used, and you pass the "index" around as the name.
Entities may have an actual string name, but you won't be using that to find the entity by name very often; generally speaking, you will reference entities by either pointer or index. This is still an associative array; it just uses an index rather than a name as its key value.
One pitfall you may have with associative arrays is that you may need to collate entities based on different properties. Things like "find all entities with blue hands" or whatever. Your associative array isn't going to help you; you'll have to take a linear walk down the entire list of entities to deal with that.
If your game does this kind of collation a lot, then adding other data structures might be a better way to go. Of course, that's rather complex.
std::map
std::map is a specific implementation of an associative array. And while it is the shortest associative array in the standard library, it has certain performance quirks.
Specifically, every insertion is a memory allocation. But more than that, because the memory is likely not contiguous, accessing different elements will likely miss the cache. If you ever need to walk through the list of all entities (to render them, update their position, etc), every entity is basically going to be a full cache miss.
You can read more in this PDF; it talks about std::set, but they're both the same under the hood.
The "conventional wisdom" I stated earlier tends to avoid that issue. But really, it's bad coding for C++. It's really just a poorly-designed pool allocator, and an actual pool allocation system would be far better at achieving the same effect.
A better alternative would be using Boost.Container's flat_map class. It essentially takes the concept of a sorted vector from the PDF and implements a variation of set and map from it. Insertion and deletion will be slightly painful, as it will have to shuffle elements around. They'll be more painful than the pool allocator case, certainly. But iteration will be quite fast.
However, what matters most is that you think about how much this matters. Is your game performance heavy at all? More specifically, is your game's performance going to be contingent on the memory performance of the class that contains your entities? If not, then what matters for you is user convenience. Do what it takes to get the job done. And if map does the job, use it. If it starts to become a performance issue, you should be able to replace it with something else.

+1: Almost exactly what I would've said but you put it much better than I could have, plus I learned about boost::flat_map from this.

Take blanket statements like that with a grain of salt. Only a tiny fraction of the code in a game is performance sensitive. If a map is the collection you need, use it. Otherwise don't.
You're trying to be specific with an example of holding a bunch of "GameObjects" in a map. What are you mapping to/from? Why do you need to sort your GameObjects? If you can answer both of those questions well, then a map may very well be what you need.
From my experience, when dealing with any sort of entity system, the entity container does not have any additional data that needs to be stored outside of the GameObject, nor does the container have to be sorted. I just need everything in one place so I can quickly complete actions on all of them, an array or vector is perfect for that.
But perhaps your game, for some reason, needs a LOT of arbitrary communication between GameObjects. You give each GameObject and ID and want to be able to tell your container to get another GameObject by it's ID. After some profiling, you realize that searching through an unsorted array of GameObjects is your bottleneck because of how much searching you have to do. You figure you can refactor the ID outside of the GameObject and you want your data to stay sorted to make searching quicker. In this case you could try replacing the array with a map and see if there are any noticeable performance improvements.
On the other hand, there is something to be said about a map not being stored contiguously in memory. Looking at it through a data-oriented programming lens, maps (and all hierarchical data structures) are a nightmare. Flat data structures have less iteration overhead and cause less cache misses. Additionally, it makes parallelizing code much easier. Give each thread an index and a length and tell them to go. Assigning nodes to threads from a tree is significantly more complicated.

A data structure is a tool, like any other. That means it has places where it is appropriate and places where it is not, and a map is no different.
If it fulfills the need of your program, makes logical sense in the use case and contributes to the improved readability of your code, then use a map.
If that use case ever becomes a performance concern (which you'll know through regular profiling of your game), address that concern then.
You've provided no references or citations to the assertions that maps have no place in game development, but if you had I suspect those claims would be easy to dismiss as overgeneralized hand-wavy FUD.

Ill add that it's also very dependent on the data you're modelling, and the operations that you perform on the data. If you're just writing something simple, you're not likely to suffer the same performance problems that people who are actively pushing the hardware very hard.
Maps, or associative containers, as your diagram suggests, are fantastic for random access patterns. they're not so great for linear access. They're also pretty decent for when you need to insert and remove a lot of items. being STL, they're also going to work with very very minimal bugs (read "if it breaks, its 99.99% your code).
As always make it work first, make it fast later. The key to doing that effectively is good API design which is optimised around your access patterns, but hides the underlying data structures. Once you've got it working. profile profile profile. Its quite likely that any performance issues you will have wont be based on your usage of std::map.
The only data structure you should try and avoid at all costs is the linked list. They're terrible for linear processing due to being cache inefficient, and they're horrible for random access as you have no way to jump to a particular node without iterating the list. doubly linked lists are somewhat better, but you're far better off just using an array, or a tree.


text:
How to deal with objects placed in the root nodes of a quad tree?
I've implemented a quad tree where points and axis aligned rectangles can be put.
It works fine, except for one issue that I'll try to describe.
When you put a rectangle in the tree and this rectangle collides with quadtree's node borders, than your rectangle is put in parent node of that node.
It's ok! That's how it should work!
Let's consider I have a small rectangle (red) laying in quadtree's center (x: 0, y:0). And I would like to retrieve other rectangles near my rectangle (blue rectangles). But here's the problem, when I do that the algorithm will return all rectangles(blue + green), because my rectangle collides with quad tree nodes border and is put in quadtree's root node. I don't need green rectangles and I can't allow myself to have such an overhead.

How can I avoid such problem? What would be the easiest way to implement solution to this problem?
The current Retrieve method recursively walks to each subnode of the node where red rectangle is positioned.
I've heard about overlapping node borders solution, but I guess it won't help in case if red rect would be 3x time bigger?!

What kind of behavior do you expect exactly when you say "And I would like to retrieve other rectangles near my rectangle (blue rectangles". How do you define near in you context?

Near - it is in same node where rectangle is positioned.

From what little bit I have read up on quadtrees, people tend to only store at the leaf nodes. They will have a pointer to the objects within these nodes and if your object is in multiple nodes you simply just have a pointer to it in each node. You can iterate through the quadtree to figure out how many nodes your object is in and only take objects from those nodes. However then you run into the problem of having multiples of one object. I think they used a hash of some type to store the pointers that way it removed duplicates.

When I did a quadtree in school, "only store at the leaf nodes" only made sense if you had a set number of subdivisions. But then, a large object would take up about 37 different tiny leafs. It becomes complex to resolve only sub-leafs if you have a world with both bullets hitting tin cans, and large trucks crashing into garage doors.

@Katana314: theory points out all kinds of problems with these data structures that just never occur in practice.  You will never have so many bullets in one area you end up generating a bazillion tiny nodes, and if you do have that many, just place a limit on how many subdivisions you allow.

BTW related with a very nice answer: http://gamedev.stackexchange.com/q/14373/30949

If you re-implement your quadtree to insert objects on borders into all siblings of that border, then the result you'll get is exactly the result you are trying to achieve (with an overhead of 2n per object where n is the number of borders the straddling object is in contact with.)

+1 That's right. Just be sure to remove the duplicate references before you return.

I don't understand why do you add the green ones? If you simply test in each step if the red overlaps with the child (simple test), it would look like this:
Let's say your rectangle red is located in root and you want to retrieve the neighbours and put them into result
child = root

procedure populateResult

  if red collides with child
    add all neighbours located directly in child to result
    if child.hasChildren
      for each child
        call populateResult(child)
      end
    endif
  endif

And this should only add the blue rectangles.

Because red collides with all four subnodes of rootnode.

But the greens and blues are not located there, right? They are located in their children. So just pick the 4 children and repeat.

I have also implemented an open-source QuadTree with a friend, and we store all objects that don't completely fit into child quads in the parent quad. This can happen at any level of the quad tree. Any time an object straddles the boundary between two quads, it needs to be stored at the parent level. When you are querying the tree, even if you're looking at some obscure corner of the earth, you need to be checking these boundary objects all the way down the tree. Here's some very rough pseudocode for a quad:
List<object> storage;

// Note this is called with the root "quad" and is called recursively
Insert(object, quad)
{
    If the object fits completely inside the NE quad, Insert(NE), return
    If the object fits completely inside the NW quad, Insert(NW), return
    If the object fits completely inside the SE quad, Insert(SE), return
    If the object fits completely inside the SW quad, Insert(SW), return
    Else, insert it storage (specific to this quad)
}

List<object> Get(area, quad)
{
    Check each object stored in storage
    Check sub quads recursively (which will in turn check their own storage)
}

It might sound wasteful to store boundary objects like this, and you may get a number of these, but it's not that bad, and there's no choice if you want to store areas in your tree. You could store points in the tree, but then area-based queries break, and that's a more common use-case.

authors: Инга Куценко


text:
Three.js camera rotation and behavior
I'm just getting into Three.js and the camera is causing some problems. Basically, I want to implement spectator-like movement controls, so that I can move around freely in the scene. The problem is that the camera seems to have it's own coordinate system, so rotating it rotates the camera, while the system itself is left untouched. This, in turn, causes problems when moving the camera.
To better illustrate the problem, please have a look at the scene. Use the arrow keys to look around and press w to move forward.
http://jsbin.com/anarid/1/
Ideally, I'd like to apply the rotation to the 'whole' camera instead, including its coordinate system. I know that Three.js provides controls, but I'd like to implement them myself for learning purposes. I also know that a lot of people do have this problem and that there are a couple posts dealing with this. However, I mostly fail to understand the solutions. If someone could shed some light on this, I'd really appreciate it. :)
Greetings

You don't move a "whole coordinate system."  The world coordinate system is meant to be completely independent of the camera (you might even have more than one camera, after all).
Take your movement vector, apply the camera's world-space rotation, and then add that the camera's world position.  It's as simple as that.
That is, if you want to move forward (negative Z for sake of example), you'd have a movement vector <0,0,-1>.  If your camera was turned 90 degrees right then after applying the rotation matrix to this vector you'd get <1,0,0>.  Now add this vector to the camera's position to move along the positive X axis, which is the way the camera is facing and what you wanted.

Thanks for the answer. I was able to fix the movement, however, the rotation is still behaving rather unintuitive. With the forward movement fixed, how would I go about fixing the rotational behavior? Right now, you can rotate on the x axis just fine, but if you use y afterwards, it still doesn't work as expected. (Just as in the code above)

Sounds like you're just calculating the matrix wrong.  Could be one of a dozen things.  If you implement your camera as a pair or triplet of vectors, make sure you rotate them all as appropriate, renormalize, and reorthagonalize where needed.  That is, if you have forward and up vector, make sure you rotate both when looking up or down.

I am creating a Third Person game and i just add the player mesh to the camera like this.-
camera.add(charactermesh);

That is a simple way of moving the camera with your mesh.Hope this helps

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


text:
How significant is the addition of multiplayer to a singleplayer game compared to starting with multiplayer in mind?
Especially for game designers or software engineers, I was wondering how significant of an increase in difficulty/frustration/workload it would be for multiplayer to be an afterthought of a singleplayer game, as opposed to putting in all of the work for the game to be "multiplayer ready" from the start.
This question is especially important when the question of "Will there be multiplayer?" is up in the air until after the game is developed.
I only ask because coding with multiplayer in mind from the start, I assume, is a hefty chunk of extra difficulty that one could otherwise skip. Of course adding in such a engine-changing feature, I assume, would be quite frustrating given a game already close to being finished. Both strategies seem burdensome, but if the extra workload of implementing a big feature after a game is already completely is extraordinary compared to the heavy workload of engineering it from the start, then obviously one would nearly always want to prepare for multiplayer.
I am also curious on a personal level as I have seen a few indie projects declare they will never add multiplayer, and then months later after the game has over a year in development, change their mind and say they will be adding it as a high priority feature due to the large demand for what is probably the most common core feature of any game.

Online multiplayer, LAN, or split-screen?

Related: http://gamedev.stackexchange.com/q/34064/18913

Online Multiplayer or LAN

You could write the singleplayer as one man multiplayer, e.g. so that the client starts a server running on the players computer and connects to that when a singleplayer game is started. Even then, the networking required is non trivial.

There are software architecture patterns which make it quite easy to add multiplayer later. One is the Model-View-Controller pattern.
In a game, the model is the current game state (which game object is where and does what right now), the view is the graphic engine which visualizes the game state, and the controllers are the game mechanics and the player inputs which change the game state.
To add networking or multi-controller support to a game built around MVC, you just need to add a new controller (network input / 2nd player controls) and a new view (network output / 2nd player screen).

Thank you very much, this is a very detailed and specific answer.

-1 A good multi player is far from easy. It opens a new dimension of problems, design patterns will be the smallest of the problems. Testing and debugging is a pain and timing critical, Qa-ing, bug-reproduction, a new wall of TRCs and TCRs or whatever your platform's compliance tests are if any.

Definitely the best answer. Very sad it has the least upvotes, but you probably don't spend enough time on the website to be friends with the group of users who pat each other on the back with upvotes regardless of the answer's quality.

@MannyTotem there is no conspiracy - my answer was just too late. Late answers always get fewer votes, because most people overlook them and only vote on the answers which are already on top.

Too late by 1-2 hours?

@MannyTotem How much later doesn't matter - people only look at the order. Check out some of the trivial questions for highly-frequented tags (like Java or C++) on stackoverflow - you often have a dozen or more almost identical answers, with the one which was just posted seconds before the others having far more votes.

I don't agree with this answer. I don't think the low number of upvotes has anything to do with timing. I notice that none of the other answers have any downvotes, while this has 3.

If you were to compare a list of all the systems that could be affected by the addition of multiplayer with a list of all the systems that need to be in the game, the lists are likely to be the same.
For example, adding multiplayer to a single player game can/will affect:

Enemy AI (now the enemies have multiple enemies!)
Rendering/animation (if you had a FPS before, now you need to also draw a character where the camera is, animations that look fine in first person may look horrible to another player in 3rd person)
UI (lobbies, chat windows, etc.)
World structure (that chunking system now needs to support multiple locations)
Save/load data (changes to the world can come from other players and need to be saved)
Sound (local multiplayer now has two listeners and Maik's other examples in comments)
And so on...

So, how significant? Very significant.
However, I would purpose it's better to finish a single player game than to never finish a multiplayer game. If you have doubts about the added difficulty of completing a game that includes multiplayer, don't include it. You can find a middle ground along the way, by trying not to make architectural decisions that will shoot you in the foot later, if and when you update the game to be multiplayer.

I am not sure your list is entirely accurate. It would be extremely archaic if multiplayer networking effected something as client-based as Sound. I won't go into why I think other things on the list are not very relevant to multiplayer, as that can sometimes be true depending on how you design the game. However something as simple as sound would definitely be almost entirely on the Client, and would be the result of an event, not actual network data telling players to play a sound. I suggest an edit to clarify why these things are listed, or to delete a good chunk of them from the list.

@MannyTotem Thanks for the suggestion. I believe that as you say "it depends". The point being it has the possibility to affect all those things. Perhaps not for your game or the way you're designing it, but it's possible with another game with a different play mechanic. I'll leave the answer as it stands to be more generally applicable. Feel free to ignore any of the items on the list you don't think fit your game. Just understand that the point is: it's significant.

I would still love to see the list have explanations for how it can affect the listed components. Note that I said "clarify why or delete" as opposed to simply "Erase that answer ya fool!" lol :P It would give more insight as to how networking could work, more credibility to the answer, and just create a better answer to what can only be a very commonly asked question.

@MannyTotem I've added examples and removed sound (couldn't think of a scenario for that one :p).

Sound changes in fact with local multiplayer, now you have 2 listeners. Another scenario is calculate shooting and collision on the server, but the impact sounds must be triggered on the client.

Or stream randomized voice over's that must be in sync and streamed on server and client synchronously. Or voice chat ..

Thanks @MaikSemder Those are good scenarios. Local multiplayer is a good example.

Thanks, good example and a much more improved answer! This is what the site is about.

This is one of those "it depends" questions.  Does your game have a lot of physics objects that would be hard to replicate?  How much would high latency bother your game?  What kind of libraries are you using?
And on top of that, does the design of your game allow for multiplayer?  Shoving co-op into a single player corridor shooter where you have your designers making assumptions about the numbers of players for things like traps and puzzles isn't likely going to work even if you solve the technical problems.
Some games go so far as to have separate single player and multiplayer executables and just share art content and style.  So you can have multiplayer but you basically have two separate code bases.
Suffice to say, it can be incredibly difficult or fairly easy.  Obviously the better you can plan the more you can do.

The design aspects that Tetrad points out are most keys.  Solving the technical hurdles is often quite doable, especially if building on an engine that already has it, but making the actual game fun and engaging with both single and multiple players is a massive design challenge.

@Sean Middleditch Solving technical problems and solving design problems are pretty similar, in that a certain skillset is used to solve a certain problem. What may be difficult for a programmer might be easy for a designer, or vice versa. These are two entirely separate skills and problems. I fail to see the purpose of your comment, except to add a "Me too!" which is discouraged according to the site's rules. A simple +1 upvote would suffice, thank you.

@Tetrad I do not mean to be rude, but this doesn't really answer the question. I am a little perplexed as to why it has received 8 upvotes, when it would be much better served as a comment. Especially given the fact half of the answer are questions for the asker and a non-answer of "It depends." If this were a comment instead, the question could then be edited to be more specific and thus get a real (better) answer.

Not to mention it would result in a better question.

@MannyTotem I'm answering the implied question of "how do you determine how hard it would be to add MP to an existing product."  If you actually asked how to add MP to a specific product it would probably be too localized to generate generally useful answers. Plus you gave no details so it would be hard to really answer your question. The upvotes show that other people agree with my assessment.

Plus, if I were being pedantic, is there an actual problem to be solved by your question? It feels like a "why do other game developers say this" instead of "I am having a problem".

@MannyTotem: not quite the same.  Adding multiplayer to a game doesn't just require a little refactoring in design; it can require completely redoing the whole game.  At the AAA level this is completely unfeasible which is why you usually see it tacked on as an extra mode, quite often by an outsourced company that has no input or control over the single-player mode.

I'll have to give credit to Byte56 for admitting that it's true, as opposed to you two who deny the fact this answer is much better resolved as a comment. The upvotes do not signify agreemnt as much as they signify other high rep users patting each other on the back. This is clearly seen with the high rep users having double the upvotes of the lower rep users who provided just as good or better an answer, yet receive significantly less acclaim for it. 'Good ol boy' attitude result in upvotes. Sorry, but it's the truth around here.

I admit to nothing :) I think Tetrad's answer is the best one here. Though, I guess I'm just part of the high-rep-conspiracy ;)

If your game architecture doesn't support info coming in over the wire, it is a real hassle to add MP later. Make the decision early whether or not your first published version will have MP or not, then develop toward that goal.
It's always easier to drop the MP later if it's going to be too expensive than to tack it on if you decide you want it.

+1 vote for "It's always easier to drop the MP later if it's... too expensive..." However, I would love to read a more in depth reasoning for WHY it is a "real hassle to add MP later" or a personal experience as to the level of headache caused by such a hassle. Some more meat to this answer would be very beneficial to anyone reading. Thank you.


text:
Auto-organized / smart inventory system?
for the past week I've been working on an inventory system with Unity3D. At first I got help from the guys at Design3 but it wasn't too long till we split path, because I really didn't like the way they did their code, it didn't have any smell of OOP whatsoever.
I took it further steps ahead - items take more than one slot, advanced placement system (items tries their best to find the best close fit), local mouse system (mouse gets trapped in active bag area), etc.
Here's a demo of my work.
What we would like to have in our game, is an auto-organizing feature - not auto-sort.
We want this feature because our inventory's going to be in 'real-time' - not like in Resident Evil 1,2,3 etc where you would pause the game and do things in your inventory. Now imagine your self in a sticky situation surrounded by zombies, and you don't have bullets, you look around, you see that there are bullets nearby on the ground, so you go for them and try to pick them up, but they don't fit! you look at your inventory and find out that if you reorganize some of the items, it will fit! - now the player - in that situation doesn't have time to reorganize because he's surrounded with zombies and will die if he stops and organizes the inventory to make space (remember inventory in real-time, no pausing) - wouldn't it be nice for that to happen automatically? - Yes!
(I believe this has been implemented in some games like Dungeon siege or something, so sure it's doable)
take a look at this picture for example:

Yes, so if you auto-sort the issue you will get your spaces but it's bad because:
1- Expensive: it doesn't need a whole sort operation to free those spaces, in the first picture, just slide the red item at the bottom to the very left, and you get the same spaces that you got from the auto-sort.
2- It's annoying to the player: "Who the F told you to re-order my stuff?"
I'm not asking for "How to write the code" for this, I'm just asking for some guidance, where to look, what algorithms are involved? Is this something related to graphs and shortest path stuff? I hope not cuz I didn't manage to continue my college studies :/
But even if it is, just tell me and I will learn the stuff related.
Notice there could be more than just one solution. So I guess the first thing I have to do is figure out if the situation is 'solvable' - if I know how to determine if a situation is solvable or not, then I can 'solve' it. I just need to know the conditions that makes it 'solvable'. And I believe there must be some algorithm/data structure for this.
Here's a pic for more than one solution of trying to fit a 1x3 item:

The arrows show just one of the solutions, but if you look you will find more than one.
This is what I ultimately not auto-sorting but find a solution and applying it.
Note that if I spend time on it I will come up with a way to solve it, but it wouldn't be the best way, it's like, holding a car wheel with your feet instead of your hands! XD
Or just like trying to solve an issue that requires arrays, but you're not yet aware of their existence! So what is the right approach to this?
Updates from Commentary
@Stephen I'm really no guru in Alogs, you mentioned 'knapsack' and @BlueRaja - Danny Pflughoeft mentioned a 2D bin packing algo. Are they somehow related/same? - I'm still confused as to how should I approach this.
And yes I'm already using a "heuristic" but I didn't really know that I was :D it finds the first available slot, and see if the item fits there.
I don't know if ordering items based on their "bulkiness" (which I call nSlotsRequired=nRowsReq*nColsRec) would work, because you have a 2x2 and 1x4 items for example, they have the same bulkiness, but different shapes and will have a different effect on how the rest of the items next will go. SO... :/
I watched this video, I really liked the full packing idea, but I wonder how to go about it since the inventory is 2D. I'm not even sure that bin packing is the key here because, well it's true that I can have more than one bag, but in our game it's just gonna be one bag. So, it's a matter of fitting items in 'one' bag and not more than that. So the examples in that vid (the pipes and buses) don't really match with my problem. Also watched some stuff about this knapsack thing, I didn't see how the 'value' is related to my items/inventory, but I guess 'weight' is the same as bulkiness, not sure.

This is 2D bin-packing, which is NP-Complete.  So, any algorithm that will tell you if you can fit all the items will be inefficient (in the worst case).  You can find some pretty good approximation algorithms, though.

This is exactly why I decided on the (more common these days) one-slot-per-item type inventory model instead of this.  I wish I had a solution for you, I gave up on this problem...

@BlueRaja-DannyPflughoeft I wonder if a simple/efficient algorithm is available if the items were limited to certain shapes?

Limiting shapes doesn't reduce the complexity but just makes it easier to think about so you think the complexity has been handled, afaik.

@VeXe Sorry I missed the update on your question. Bin packing and knapsack aren't the same. But both are packing problems. The 'value' in your case is the shape and size of your inventory objects.

The usefulness of ordering on bulkiness is dependent on how you calculate the bulkiness. That's why I mentioned several ways to calculate it.

"2- It's annoying to the player: "Who the F told you to re-order my stuff?""
Well actually this auto-sort technique is employed in Deus Ex: Human Revolution and I didn't find it annoying.

This is a variation of the knapsack problem. As Danny Pflughoeft mentions it's NP-Complete. Meaning that it can't be solved in linear time, if I remember correctly.
But you can try to solve this in several steps. It's basically a sorting problem.
I would start by calculating the 'bulkiness' of each item:
this could be calculated several ways:

bulkiness = max(length, width);
bulkiness = length*width
bulkiness = sqrt(length*width)

Then start putting items with the highest score first into the inventory. Since they most likely won't fit into the remaining space later. Small items will fit always.
You need an heuristic (a fancy name for educated guessing ;-) ) for your placing strategy. Something like trying to fit items in the first free slot from top-left or something.
Diablo II inventory sorting strategy worked somewhat similar I think. Stuff like swords and spears would end up top left, then clothes and armor, then buckler and so on.
I think you really need to try this out and tweak the algorithm (different bulkiness calculation, different heuristic), until it works reasonable enough.

NP-complete is a set of problems with complexity higher than polynomial. For a relatively small inventory (less than thousand items I'd say :)) even exponential algorithm would work pretty fast, because one step of such algorithm takes very little time. Nevertheless using your idea should be good enough and easier than implementing a dynamic programming algorithm -> +1

thx for the upvote. Yeah the inventory shouldn't be potentially infinite so exponential algorithms should work fine ^^

@sm4: A thousand is typically an enormous number for NP-Complete problems.  Remember, these problems are O(2^n) - even just 2^64 is computationally infeasible!

Haha, @Everybody who helped, thanks. I managed to finally solve it. Here's what I basically did:
IEnumerator AddItem_Sorted (Item item)

Trivial condition: check if we got the min nRequiredSlots for
the item to fit in, if we do have it, proceed...
we'll empty out all the bag - putting the items in a placeholder
(list or something)
add the wanted item to the VERY last slot/place it could fit in,
making sure it's sure in its horizontal shape
using the first-fit decreasing algo we'll add the rest of our
items
during the adding, we'll use dynamic programming (memoisation)
to remember that index that we're adding at (index of next available slot)
if all adding is success, we have managed to fit our wanted
item, and somehow sort the bag - from big to small items
if we couldn't add all the items, this means that, this wasn't a
solvable situation, so we have to get the bag to its previous state
one way to do that, (came out of my mind's surface), is to copy
the state of the bag before this whole opperation, and then if it
fails   we'll snap to that previous state, or even better, in during
the 'emptying' of the bag, we memorize where each item was, so that
    if the op fails, we'll get them back - using AddItem(item, index) -
at their previous indices :)
this whole process might take time, so we could divide the load
on separate frames, using my lovely yield :)
DONE! \m/ (@~9:00)

UPDATE:

I made an array that stored the indices of all the added items, that
way I don't have to go and look for the occupied slots for me to
free - big boost.
no need to add at the last slot, in fact sometimes it might not
work that way, I've added the wanted item to the rest of the other
items and sorted it with them.

As you can see from the video, it needs a bit of optimizing, the sorting is not perfect, I would like to use full bin packing, but it's already performance-greedy.
I'm open to any optimization suggestions, thanks again :)

You're welcome! :) I'd like to thank BlueRaja - Danny Pflughoeft for mentioning bin packing, @Stephen for the bulkiness idea and Richard Buckland for his dynamic programming lecture, and all lectures.


text:
how to calculate sky color hue in a specific way?
I have a day cicle in my game.
I want to add a bluish hue to my terrain in the early morning and evening-night.
I want to start transitioning from 0 hue color to the full hue color at 20 PM and reach the full color at 0 AM, then start fading back and reach 0 hue color at 7 AM.

Given a time of day in hour and minute, or seconds, how can I write a function to calculate the hue color correctly?

If you want a somewhat more realistic formula, see e.g. "A Practical Analytic Model for Daylight" by Preetham, Shirley & Smits.

It sounds like you want a simple implementation. So here's what you can do.

Pick your night-time hours. It sounds like you want 8pm to 7am (11 hours)
Pick your formula. Is it linear transitions all throughout, or is there a time of "constant" daylight? Let's assume you always want the time moving.
Experiment in an image editor. Take a screenshot of your game, overlay a blue layer, and see what the maximal transparency is that you want -- say 50%.

If you decide on these parameters (tweak to your liking), the rest is easy; you just need a formula for changing the alpha. It will start at 0 (8pm), and at 0 (7am), and peak at 50% (1:30am).
The formula should be pretty easy to calculate from this. You use the time difference from now to the peak time, and use that to swet the alpha of the blue overlay.


text:
projected textures not appear on the "back" of the mesh as well?
I want to create blood wounds on my character's bodies by using projected textures. I've watched some commentaries on games like Left 4 Dead and they say they use projected textures for the blood.
But the way projected textures work is that if you project a texture on a rigged character, say his chest, it will also appear on his back.
So what's the trick? How to get projected textures appear only on one "side" of the mesh?
I use the Panda3D game engine, if that will help.

It sounds like you are using ancient projected textures in a fixed-function pipeline. If that is true, you will not be able to solve your problem without a custom shader that checks the dot product of the blood-inducing vector to the vertex normal.
However, if you can use programmable pipeline, you can abandon 90s and venture forth into 21 century with decals. Decals are being used for tasks such as blood marks, explosion craters, wall posters, etc. since forever.
Chances are, L4D devs meant that they used decals which were projected geometrically onto objects. Nice article about these decals can be found here.
If you're stuck with fixed pipeline, I guess the best approach is texture blending. For example, prepare bloody texture of some limb, and then blend it with the limb texture when said limb gets hit.

But in L4D the texture is projected on animated models. Will this work on animated models?

It is, of course, also possible to do skinned decals. The only difference I can see is that for an animated models you have to adjust the decal frustrum, so decal position will be adjusted back to the bind pose.
For example, here is one way of doing it. Represent the decal as a sphere and find the biggest colliding bone in current animation. Let's call it decalBone. Also let's say it stores the per-bone transformations in decalBone.Offset, and it's possible to get world transformations via decalBone.WorldTransform. Then your adjusted transformation will be something like targetDecalTransform = Matrix.Inverse(decalBone.WorldTransform * decalBone.Offset). Use it to adjust the raw decal frustrum centered on the world position.
With this frustrum you can now do the same thing you've already done with static model decals: get affected mesh faces, clip them against frustum, triangulate the resulting faces into decal vertices, calculate UVs and transform vertices to the mesh local space.

But in L4D the texture is projected on animated models. Will this work on animated models? As far as I know if the model moves or animates, the texture won't stay in place. That's not the case with L4D.

@user975135 I've edited answer a bit, hope it helps.

Alternatively, you can combine your approach with shadow mapping in order to make it work dynamically and get correct occlusion.  If you create a camera that renders its depth information into a texture set to the Texture.FT_shadow filter type, and then use a combination of texture modes (or a shader) to only apply your projected texture where the shadow map compare succeeds, that should do the trick.


text:
How to deal with lot of textures in one draw call?
I'am currently developing text rendering & some kind of tile based texturing for simple landscape with textures blending. e.g. something like this but in 3D.
In first realization I have been used 2D texture arrays to achieve problem of texture switching to be able to draw whole landscape mesh at one opengl draw call and it works great, but this should run on opengl es 2.0 devices and they are don't have 2 texture array support. So my question is - what can I do to deal with that kind of problem?

Of course i can just draw every landscape quad separately, but I'm pretty much sure, that this solution will really, really heart the performance. (mb i wrong?)
Also i know about texture atlases, but can I guarantee that I can put all possible textures into fragment shader for every possible tiles  combination?(terrain tiles for landscape & every possible text chars with different sizes, I think you get the point) I almost sure that i can't, that's basically why I'm asking this question here.
Sorry for my horrible english, I'm working on that.

The first thing you should do is to just get something on the screen and have it render a landscape. If that means rendering every landscape quad in a separate draw call then so be it.
Next, determine how slow it is exactly. Scale your landscape to the size you will most likely want in your game, for example 1000 x 1000 quads.
Now you can start looking for optimizations. Do you need to render the entire landscape or only the portion visible to the player? If not, try using frustum culling to only render the tiles that are actually visible.
If it's still too slow after frustum culling, then and only then can you start thinking about using a texture atlas. Determine the maximum texture size your target devices support, for example 4096 x 4096 pixels. You can use a tool like Texture Packer to create your texture atlas.
Group the terrain textures and try to make them fit in that space. Maybe the grass texture needs lots of detail, while the snow texture doesn't need much at all. In that case, you could make the grass texture 1024 x 1024 and the snow texture 128 x 128.
Play with different sizes until you have a good trade-off between the size of the atlas and the rendering speed.

I already done with just get something on the screen, the problem is that, if i switch to separate draw calls, i have pretty much bad performance when i draw even 1 plane with, lats say 5000 quads.
And i would probably have more then this one plain, and "texturing" will be done throw the tiny helper application, so i can't really now what combination i can have and so on.
And i already done some simple culling, the question is not really about that, but thank you VERY MUCH anyway. I will try somehow your solution about balancing sizes to get good trade-off.

Actually, even if your answer is not direct answer to my question i will accept it since i just thought that i don't know something and going to the wrong direction. Now i think that i know pretty mutch all i need and just need to think about whole problem again write lot of tests to achieve acceptable performance.

You can pack textures at runtime.  You just have to load the files into CPU buffers, run a box packing algorithm, then upload the result as a single texture to the GPU.  Doing it offline is better usually, but if you can't for whatever reason, do it at runtime.


text:
Camera angle for dimetric projection
I have a simple 3D engine and I want to make a isometric(dimetric) game, but where tiles are not real 3D planes, but 2D images like this one:

As I understand this tile is drawn in dimetric 1:2 projection
But I can't get right camera angles in order to have view, where all given tiles would fit perfectly by pixel.
After reading this page
I've tried rotating camera relatively to itself by x=26.565deg y=45deg but that gave me bad result.

It's clearly visible, that tiles don't fit together nicely.
I've tried different value, by just handpicking them, and the closes one was x:30deg y:45deg angles.

But there is a problem with gaps between tiles. It maybe somehow related to problem, that I don't know how to calculate length of one tile edge in world space, currently when I put tiles in scene I space them by 45units, which also is a handpicked value.
You would ask, "Why do I try to do this in 3D engine?". I want to mix 2D tile and object sprites with simple 3D objects in one game. I've already did isometric terrain with 2D engine, where everything can be simply calculated and doesn't need to position a camera.

I love style of the "Isometrica" from the link you posted! Reminds me of The Rollercoaster Tycoon! Try looking for some clone of the game with opensource code. Might come in handy :)
http://www.facepunch.com/showthread.php?t=1149898

Dimetric projections actually don't have a "right" measure. You just have to have to axis with equal angles, with the other being any angle you want. BUT if you want like the older "isometric" 2D games, with 2:1 ratio, you can achieve this with Yaw: 45°, Pitch: 35.264°, If you want the precise angle of pitch, you can get it by arctan(sin(45°))

Btw follow the wikipedia link, it even teach how to make the rotation matrix for this.

Gustavo Maciel, I know that there is infinite variation of dimetric, but I'm looking for one that would fit my given tile sprites. 35.264deg gives way too bad results, and as I understand this angle is for TRUE isometric projection, it described here http://www.gandraxa.com/isometric_projection.xml .

Ok, got it!)
It turns out that 30deg angle is perfect for this, I can't prove it matematicaly but it works.
Problem with gaps also dissappeared, when I spaced tiles with distance of 45.261 between each other. 1/2LENGTH_OF_TILE_SPRITE_32PX * (1/Cos(45)) = 45.261.

I've been trying to get my 3d models line up with the 2D tiles I have used in Unity in an isometric view. Turns out its technically a 'Diametric" view and through experimenting I have found that placing an orthographic camera at Z-45d with an X value of 60.5d has resulted in them almost perfectly lining up. I'm not a math guy by any means no idea why it is, but its working. Hope this helps someone!


text:
Cocos2D SpriteBatchNode vrs. SpriteFrameCache… I do not see any performance difference
I have tried using both ways...

adding the .png file on the cache with SpriteFrameCache..
adding .plist with spritebatchnode adding the correspoding .png file, I didnt see any performance difference.

In my test I keep adding and adding objects with the same image.. in this case a bullet... eventually the app crashed because it ran out of memory. Same thing happened to both situations with SpriteFrameCache and SpriteBatchNode they both dropped FPS to 30(when its supposed to be 60) and then just crashes...I understand the scenario is not real.And obviously its destiny its to crash if I just keep adding images without destroying objects that are no longer in use...but the question remains.
I saw the same performance issue, however I read that SpriteBatchNode makes only one draw call making it best performance practice. Has anyone tried and can confirm the performance difference and exactly how can you prove this performance difference in code and in the app?

Check this blog post of "Master" Steffen :).
It seems to be all about OpenGL draw calls and OpenGL state changes of the images and how large the images are and if they have transparency or not.
Try to use several "big" background images in parallax and compare the fps rate with or without batchnode.
Following I report some extracts from Steffen's post as the content of this answer should belong to him :):
On number of draw calls:

it matters a whole lot how much one sprite differs from the previous one and which OpenGL states it changes  (cit. Steffen Itterheim, blog post 8th September 2011)

Using 10 large sprites (with lots of transparency, pixel size: 480×320) and not sprite batching the fps rate went down to 15fps (see details of the article) but

Once I enabled sprite batching the framerate went up to 60 fps (cit. Steffen Itterheim, blog post 8th September 2011)
(...) for anyone who is composing their background images of multiple images (eg for parallax scrolling), sprite batching can make a huge difference even if you only have 3 or 4 different background images.(cit. Steffen Itterheim, blog post 8th September 2011)
(...) In fact, it’s the larger images that you will want to draw all from the same texture atlas to improve sprite batching performance. (cit. Steffen Itterheim, blog post 8th September 2011)

Hope it helps

Answers need more content than a link.  It's impossible to gage its quality, and it might break in the future.  Please flesh out your answer, or convert it to a comment.

@SethBattin cool, done.

Thanks it helped me out a lot to clear out my mind. So they both have to be used in order to have the FPS running efficiently. Thanks really for the answer.

Wellcome, Steffen's post helped  me understanding these things few months ago :)


text:
Minimizing amount of comparisons for collisions?
In my 'Terraria' based game I am having lag issues. The cause of the lag is as follows:

Every update loop through all the tiles in the world:
If the rectangle that was passed as an arg intersects with the current tiles rectangle return true. If not go to the next tile.
If the rectangle that was passed as an arg doesn't intersect with any of the tiles rectangles then return false.

My solution is to only check collisions for the tiles that are on the screen.
At the moment my code renders all of the tiles regardless of the position. I know that this is a very lag-filled approach and I have no idea at all what the maths is to only get the tiles the player can see. If it helps the world is stored in a hash map that is initialised like this:
public Map<Integer, Tile> world = new HashMap<Integer, Tile>();
// numeric id = key , tile = value

I have tried looping through the tiles in 2 ways:
public boolean checkCollision(Rectangle argRect)
{
    for(int i = 0; i < world.size(); i++){
        Tile tile = world.get(i);
        Rectangle tileRect = new Rectangle(tile.rect);

        if(tileRect.intersects(argRect)){
            return true;}
    }
    return false;
}

And:
public boolean checkCollision(Rectangle argRect)
{
    for (Entry<Integer, Tile> entry : world.entrySet()) {
          Object key = entry.getKey();
          Tile tile =  world.get(key);
          Rectangle tileRect = new Rectangle(tile.rect);
          if(tileRect.intersects(argRect)){return true;}
    }
    return false;
}

Could I pass the players position to this method and have it only loop through tiles in the area? Would this approach have to loop through the tiles to see which ones are in the area?

There are a couple things you can do.
First, don't update every tile every tick of the game.  Games like Terraria do periodic updates on only parts of the world at any time.  Sub-divide your tile grid into chunk.  Update one chunk each tick.  You don't need to do it any more. You might even need to do it less.  Things like growing grass and such are literally just a random check each time a tile is updated.  You can control the rate of growth by altering how often ticks are done and how rare the random chance is.
For collision, you can limit it even further than what's on screen.  In fact, for enemies near the edge of the screen, using only tiles on screen may be incorrect.
Instead, check the tiles that your rectangle could possibly be colliding with.  You have a grid world.  This is super easy.  Take the upper left position of your rectangle, determine which tile that's in. Take the bottom right and do the same.  Now you have the exact rectangle worth of tiles you can possibly be colliding with.  This is probablyl (hopefully) what you do for drawing.  Check against those.  You could even with a little extra work determine which new tiles you could be colliding with (say, if you move right, and you can only move so fast each update, at most you have to check the right edge's worth of tiles), though there's probably no reason to do that.
Note that breaking your world into chunks can have further performance advantages.  Generally, there will be one-four chunks visible at any given time.  If you lay out the whole world in rows, each tile in each row is entire world's width away in memory.  This can cause some (very slight) overhead.  Keeping things in chunks means that a whole rectangle of tiles (left to right, top to bottom) are relatively close together in memory.  If you process tiles in whole chunks at a time, this means your code runs slightly faster because more of the interesting data will be in cache at any given time.
Don't use a hashmap for your world.  A hashmap is cheaper than many data structures, but your world (or a chunk in the world) is a 2D grid.  Just use an array, which is always the absolute cheapest data structure when it is an option (and will be orders of magnitude more efficient than a hashmap in this case, I'd bet).  I don't recall if Java supports 2D arrays automatically, but if not, just remember that array[y][x] is the same thing as array[y * width + x] and carry on.
Also avoid using full objects for your tiles.  A simple integer will do if you are clever, do the world update trick I mentioned, and maybe a little bit packing.  Objects are heavy-weight heap-allocated things in Java and a big grid of tiles will be inefficient as full objects.  Likewise, avoid using operator new anywhere you don't strictly need it.  Consider passing in rectangles to collision as simpler values (either explicit, x, y, w, h or using existing vectors and rectangles from your entities).  new is not the cheapest operation, increases pressure on the garbage collecto


text:
What is actually loaded during a game's loading screen?
I am at the stage of my game where I have to develop the loading screen. It's actually already there, but I don't know exactly what it should be loading while it's presented.
Why would I have a loading scene instead of just going directly to my game scene? I don't even know what else to load besides the textures with the texture SpriteCache.
Am I doing the correct content loading? I missing something to load during that loading scene?

Typically, the loading screen is presented so the user sees some kind of activity or indication that the game has not stalled while the game loads all the necessary data to play the level (or whatever), especially when loading the data might take a long time.
If your game can already go directly to the gameplay without an unpleasantly long delay, then you don't need to implement a loading screen.

Yeah but what Kind of classes or objects need to be loaded that would make seemless the delay of the game when it has to load?
But I do understand the concept thanks. :)

It's less about the type of data and more about the amount of it.

indeed, I see, thanks... I definately understand now. :) thanks for the help.

I don't have experience in cocos-2d but in general during loading screen the game would load various assets. For example the textures, background music, sound effects files, video files if you have any or reading in any map/game data files. Some game may want to preconstruct some of the levels because they take a lot of time(e.g. randomly generated map) so once the player get into the game they don't need to wait for any loading screens anymore.
Preloading resources means that you can directly use those resources later in the game without the user waiting for them to be read in which improves the user experience. However you don't want to load every single assets you might need in the future. First is because you don't want to occupied a lot of memories for things that you might not need later. If you use too much memory the system may kill you off or it will actually affects the performance of the game due to paging. Second is startup time is one of the factors that affects user experience and generally player don't want to wait too long for starting up the game(they might just want to have a game when waiting for someone for a few minutes). In situation like this smoothing out the loading time by deferring loading or background loading may actually be a better idea.
In summary, deciding what to load during the loading screen depends on the specific game you are making. Keep tuning it until you satisfy with it :)

There's an implied question here: "When do I need to use a loading screen, and when can I do without?"
If your game is still small, you can probably let the player begin immediately with no delay. As your project grows, you might notice that the app "stalls" or hangs for a time before the game becomes responsive and the player can start playing.
If the delay before the game starts becomes noticeable, that's when you might need a loading screen. Find out what is slowing down the start of your game and do that during loading.
Of course, if you can keep everything fast enough that you never have a noticeable delay, so much the better - eliminate the loading screen entirely!

you think that the loading screen is not necessary then unless that delay becomes an issue... Thanks. its pretty much how I thought where to place it before a game starts or stuff like that but sometimes I remember seeing loading screen during a game, like Final Fantasy for example, that always made me wonder. Or like Metroid Prime Series, loading during the opening of doors, they tried it to look seemless.


text:
How to create a character animation where the parts of the sprite change?
Let's say I'm creating a game (in Java or C++). In this game I have a character that can do a sword swing animation, but the character can equip different swords.
Do I have to make an animation for each individual sword, or is there another way? I Like if a character can equip different armors, do I create a new sprite for each armor, or is there a way to have, say a base character that can perform all the animations with different swords and can have different armors on the same image?

Possible duplicate: http://gamedev.stackexchange.com/questions/1335/which-is-the-best-approach-to-make-a-2d-character-to-be-able-to-use-tons-of-diff

Related: http://gamedev.stackexchange.com/questions/43931/how-to-deal-with-character-body-parts-from-design-to-cocos2d

Yes, you can do it in a fairly simple way using transparency.
What you'd need to do would be to make a few layers of sprites instead of one, prepared in such a way and order that when they were displayed, they would form a whole person.
I've attached a sample image showing how that might look.

Shows the base image I was working on
I've removed parts that are not going to change
I've made one isolated sword image
That's how sword (gold one this time) looks when drawn over the image from 2. Smooth!

Now you can easily replace steel sword with gold sword, and you don't have to create a whole new set of sprites.
If you feel more like an artist at this point
Then simply draw a few (5-10) sword positions (precomputed). This has an additional benefit of allowing you to change the sword shape during movement and might produce overall better results.
The number of animation frames is of course up to you. What's important in this method is that with a proper sprite delay engine (not that hard to write), you can have more frames for parts that move faster and less for ones that move slower.
Simple pseudocode implementation might look like
// calculating each subpart
foreach(sprite_part in parts)
    // first_not_less_than is usually called "lower_bound"
    sprite_num = time_data[sprite_part_num].first_not_less_than(time)
    sprite = spritesheet[sprite_part[sprite_num]];

If you feel more like a programmer
Notice how I've removed the whole arm from the base. You could easily rotate the sword to simulate the movement. This will produce a very smooth animation and requires only sprite drawn in basic position, but can feel a bit less natural.
Forgive me for not preparing a .gif comparing the two, but I am not an artist :)
While this is only an example, there's of course more to it. From a top-view game or isometric game different approach can make sense. This answer only aims to illustrate the general idea.


text:
Unity3D filling visible camera area with objects
I'm developing an isometric tile-based game using Unity 3D.
I'm using an orthographic camera looking down yaw:45° and pitch:45°.
The game has an infinite world, which is loaded from a remote server. Because it is impossible to load everything at once, the game should only load visible areas of world.
But I don't know how to determine which tiles should be requested from server in order to fill up all the visible space on the screen.
I tried loading tiles by chunks e.g. 16x16 tiles chunk around camera. But this looks hacky to me and sometimes leaves blank edges visible on the screen.
Is there better solution to simulate a continuous world on the client side?

It looks like you are on the right lines with your approach of loading the world in chunks, however you may need to take this a bit further.
The way most games achieve this (a notable example is minecraft) is to divide the world into chunks of a predetermined size (16 x 16 for example) and only load the chunk the player is in, and the four (or eight) surrounding chunks. By doing it this way, you reduce the amount of data needed in memory, but prevent the player from encountering an unloaded area.

When the player enters a new chunk, you repeat the process, unloading the chunks that are now too far away (squares in red on the picture), and loading the new neighbouring ones (squares in green).

If you try this but still notice blank edges then you may need to increase the size of your chunks (or load more) to store more of the game world at a time.


text:
Cocos2d When The Loading Screen Scene is loading music
When the loading screen loads objects like music cutscenes, the idea is to preload the objects, so... what should happen next? Do I transfer the objects to the next scene? or these special objects, media objects or even just images of the sprites, do they have to be part of a Singleton? According to my logic, singleton is a simple solution, that can I use whatever was preloaded in the loading screen to take to the game. The only drawback is that I have to keep management of these objects to unload them when out of the game scene.(its just an example, but its really close to what my game is doing).
The thing is, i believe there is a more elegant solution to this problem. Anyone has any suggestions? or tell me if my method is wrong?

in Cocos2D, doesn't the music continue to play until you pause or stop it?
If I want to change music between CCScene I usually do something like:
_dir->Instance()->getAudioEngine()->stopBackgroundMusic();
_dir->Instance()->getAudioEngine()->stopAllEffects();

// click!
_dir->Instance()->getAudioEngine()->playEffect("click.mp3", false);

...do whatever

Edit:
I dont use the shared director. I created my own director object with everything I need as member variables.
I load my music like this:
void AppDirector::createAudioEngine()
{
    CocosDenshion::SimpleAudioEngine* ae = new CocosDenshion::SimpleAudioEngine();

    ae->preloadBackgroundMusic("Tallahassee.mp3");
    ae->preloadBackgroundMusic("bigcountry.mp3");

    ae->preloadEffect("click.mp3");
    ae->preloadEffect("tap.mp3");

    ae->setBackgroundMusicVolume(0.5f);
    ae->setEffectsVolume(0.3f);

    setAudioEngine(ae);
}

Edit 2:
I do this:
AppDirector* AppDirector::Instance()
{
    if (pinstance == 0) // is it the first call?
    {
        pinstance = new AppDirector; // create sole instance
        pinstance->initInstance(); // setup everything we need.
    }

     return pinstance; // address of sole instance
}

void AppDirector::initInstance()
{
    createFileUtils();

    createDirector();

    // set some defaults
    setIsHUDDisplayed(false);

    createTouchDispatcher();

    createAudioEngine(); // created and preloads music and sound effects.

    createOpeningScene();
}

how do you load that music? so you are saying that since its part of the director, I dont need to worry? But what about the other objects like sprites and animations?

see edit above.

ahhh so the singleton is the answer. by having everything ready, I just use it when needed inside the game scene right?

oh, indeed, yup my "AppDirector" class is a singleton, I create everything I need as member variables. I know cocos2d has the shared director concept, but I really felt like doing things this way provided me a lot of flexibility as well as ease of use. (at least for me)

yes, i understand I do have a singleton for several things, it does make the job easier. But so when you destroy the scene, I suppose you destroy the objects too right? like unload the music from the singleton since its no longer needed?

I made a few more edits

When I destroy a scene, I dont unload the music since I use it for various things. When I switch scenes I stop the music, load the new scene and start new music.

of course. Glad to help.


text:
how to improve sprite animations to reduce FPS
My game has different, and detailed animations throughout the game. For example, the main character has an idle stance, so its not just painted still, giving him some life. Death animation, hurt animation, etc... even the background scenario has animations(which I don't think I went with the best approach here, but, it's working for now, this will be in another thread if not answered here)
Anyways, the thing is, while the main character had these animations only that character was in the game at that time, so everything ran smoothly. After adding another character, the enemy, the burden of animations seems to overcharge the FPS and just slows the game down. The most obvious of this problems was that the spritesheet I was using was 1 per character, I figured how to use spritebatchnode efficiently and now 1 spritebatchnode covers the 2 characters animation set.
The FPS tried to get back to normal, but its still laggy at times. This worries me because my game design has more enemies to the game, meaning that it will have this issue in a bigger scale.
So I believe that its because of my animation approach, its poor, and inefficient making my game run slow.
I have been trying to find the answer online with no luck, and I don't my approach is the best. I tried working some solutions by my own, but they end up in the same thing. THE ONLY, the only way I find how to reduce this problem is to make my sprites smaller, its not a big deal, but I wouldn't like this solution.

What evidence indicates it is for sure animation?  Frame hitches could be a million things.  Have you profiled to ensure the hitches don't occur during spikes in physics, garbage collection, or do in?

you just talked to me in a language I don't understand... but to answer your question,it doesnt happen during physics(since its not completely coded yet), what I mean is when I add specific animations with Cocos2d Game engine... I used CCAction: which is an array of frames  that show an animation... but I was wondering if this was the best practice.

First, are you running on the simulator or a real iOS device?  The device runs many times faster than the simulator.  The simulator doesn't do hardware vertex processing.  So the simulator slows down quite a bit with only a little load.  If its slowing down on the simulator, that's not really an indication that it will be slow on an actual device at all.
Due to the way iOS's CADisplayLink works, iOS runs at either 60 fps (maximum) or 30 fps, or 15 fps (or slower).  So if your app suddenly takes just over 16.666ms to process a frame, you're into the 30 fps category then.
I don't know Cocos2D, so I cannot tell you how to get back up to 60 fps (try compiling in release mode?)
Anyway, if you've been bumped down to 30 FPS, you might add a lot more stuff before being bumped down to 15 fps.

I am running on the simulator unfortunately. Ahh I get your points thanks alot... I will find the way to put it on my device this week and I will tell you how it went. thanks.


text:
What's the minimum viable product to present a game to a publisher?
I am currently working on a puzzle game. I am aiming in the future to ask a publisher to publish it. What do you think could be the minimum viable product to reach before sending it. I am talking about the completeness of the work (number of levels, graphic details etc)

The completeness of the work depends on the publisher, the game, you and the relationship you have with that publisher.
Each publisher will have their own standards for what's complete enough. Further, those standards could be tighter or less restrictive depending on the relationship you have with them. If you've never spoken to them, and they don't know you, it's likely you'll need something a bit more complete than if you were taking another game to them after you'd already had one success with them.
And it depends on the game. If it's mostly complete, but critical/technically challenging components are missing, that's more risk to the publisher. The genre is also important, if your puzzle game is mostly complete, but adding additional levels is very difficult or has the potential to break other things, that's more risk to the publisher.
Additionally, it depends on you and what you've produced before. If you have a portfolio of completed games, the publisher may feel more comfortable accepting something that isn't entirely complete, because they "know you're good for it".
This situation is like a job interview. If you can convince them you can do the job, and you'll do it well, they're more likely to hire you.
Your job is to convince them that the risk of taking your game is low. You can do that either by proving that the game is complete enough to be of very low risk on its own, or that the work that still needs to be done can be completed easily by you.
Your sales skills will come into play here. You need to sell yourself along with the game. If the game is incomplete, this increases the importance of selling yourself. If the game is totally done, this reduces the importance of selling yourself. It's up to you to decide how well you'll sell, and therefore how complete the game needs to be.

Depends on the publisher, really. Some of them want to see polished almost finished products, others want to be involved as early as possible in the process.
You can probably just ask them. It's possible that they may take a look at your early demo and give you some feedback or advice "for free" (e.g. without you having to make a commitment to publish with them, for example).


text:
2D Collision detection and reaction: Rect to Line
I'm working on a little 2D side scrolling platformer with a couple of friends. The issue I'm having is the level is completely defined by points. They are just a bunch of points which when I read in I turn into line segments, thus creating the floor in a sense. I've been having a lot of issues with this because I'm trying to make appropriate collision detection and reactions but I've never really approached Rect (which my characters sprite is defined as) to a Line (which would represent the section of the floor) collisions. Now I've already tried a few things and what I put together was I treated the character's Rect as if it were 4 Lines and did 4 Line to Line collisions then finding the points where the line's collided I then used some vector math to push out the line from the box. Now as far as that goes it works pretty well IF I'm colliding with one line at a time running into it straight and not on the end points. I'm really wondering if this was a good way to approach it at all really.
What I did for the reaction was make a vector from the center of the character's Rect to the two points then I added them together to make a combined vector then divided it by 2 (so it wasn't to long) and then pushed out by that, which works, some of the time. I can't get it to work without 2 points of intersection.
My questions are: Should I instead go for some other sort of collision detection and reactions?
or
Given your character's Rect and points of intersection on those lines how would you handle the reaction for this?

Ofen, in 2d games, the collision detection is made using pythagora's theorem to calculate distance between 2 points.
You could check if the character is on a platform by calculating the distance from left and right side of the platform with the bottom center of the character.
If the distance from left and right side of the platform is smaller than the length of the platform, it means your character is on the platform or close to it. You would also probably have to check if the character is above or under it. You will probably have to set some thresold and adjust the y position of your character for it to be exactly on the platform when the character is falling on it.
To calculate pythagora's theorem, you use the following formula:
distance = sqrt(abs(x1-x2) * abs(x1-x2) + abs(y1-y2) * abs(y1-y2))

where x1,y1 is the first point and x2,y2 is the second point.