JoeJ

Members
  • Content count

    562
  • Joined

  • Last visited

Community Reputation

2526 Excellent

About JoeJ

  • Rank
    Advanced Member
  1. This one may be quite important. The typical game of someones dreams would be either much too expensive to do, or technically (yet) impossible. Some obvious things: Characters can't think, talk or walk - they can only act based on very poor artificial intelligence, play animation and recorded speech. Worlds can't be infinitely large and detailed. Etc. So if your ideas contain stuff never seen before, you should clarify if this stuff is technically possible at first.
  2. That's a typical idea for someone being new to this. I'll point some things out... If your user uses only e.g. the top left corner of the intire space, you can traverse the quadtree once until you find the top most non empty node node. You can use this node as the root for all your collision or culling queries. This saves you from treversing some top levels of the tree each time for nothing and gives the performance improvement you expect from your idea. Notice that using a single tree you already have multiple trees (each node represents a subtree), so there is rarely a need to use multiple trees with an additional mechanism to handle this. So, no, use just one quadtree and no hash table at all. There is something you miss: The scene is dynamic, things will move around. The hash table approach causes dynamic memory managenment during runtime because the usage of lists (and maps), but you don't know how large they need to be. Lets see what happens under the hood (i'll use the term 'grid' instead of spatial hasing, it's the same thing) Each grid cell needs a resizable vector to store pointers to all objects. The system allocates some memory for the list, but if it becomes too large it needs to allocate a larger chunk of memory and copy the list to the new place. This may happen severall dozens, hundrets or tousand times per frame and can become a bottleneck. So using the grid we have this: gridCell->list[obj0, obj1, obj2, ...] Also, you need to store the objects in multiple cells, and to avoid duplicates, the suggested usage of a map needs to look up the current map each time a new item is to be added. To speed this search up, the system may implement a binary tree or something, resulting in building a tree for each query. (Compare this with the quadtree approach: It uses only one tree and it's already there) So this is terribly slow, but how can we do better? Using a multiresolution grid can fix this: Imagine our finest grid level 0 has 8*8 cells, each 1*1 in size, level 1 has 4*4 cells, each 2*2 level 2 has 2*2 cells, each 4*4 level 3 has 1 cell 8*8, the whole scene Then we have a circle object with a diameter of 1.9 and we put this in a cell of level 1, because we can be sure this and the neighbouring cells will cover the intire object. To find collisions we need to look at the neighbouring cells but also at the correspondending cells an their neighbours at levels 2 & 3 to detect collisions with larger objects. We do not need to go down and check cells from level 0, because collisions with smaller objects will be found from those smaller objects. You can optimize to check only 3 neighbours instead of all 8. So this works, and because each object needs only one cell we don't need a vector of pointers per cell, all we need is: mrGridCell->obj0->obj1->obj2 No dynamic allocation or duplicates problem here. A loose quadtree is just an extension of this idea, you may start with a multiresolution grid and if this works go to quadtree.
  3. You could look at the success story of Superhot: They had a great idea of gameplay mechanic, made a free webgame everyone tried out, then it became a full game. Notice that nobody stole their idea. They used Unity engine which people say is beginner friendly. I would not rush to talk too much to strangers by Email - they have more experience so it's a lot easier for them to turn it to money on their own. Forums like this can help to solve specific problems without the need to expose your idea. You need to strip down your vision to the bare minimum (which may be still a year or more of work to get something going).