• Advertisement
  • Popular Tags

  • Popular Now

  • Advertisement
  • Similar Content

    • By akshayMore
      Hello,
      I am trying to make a GeometryUtil class that has methods to draw point,line ,polygon etc. I am trying to make a method to draw circle.  
      There are many ways to draw a circle.  I have found two ways, 
      The one way:
      public static void drawBresenhamCircle(PolygonSpriteBatch batch, int centerX, int centerY, int radius, ColorRGBA color) { int x = 0, y = radius; int d = 3 - 2 * radius; while (y >= x) { drawCirclePoints(batch, centerX, centerY, x, y, color); if (d <= 0) { d = d + 4 * x + 6; } else { y--; d = d + 4 * (x - y) + 10; } x++; //drawCirclePoints(batch,centerX,centerY,x,y,color); } } private static void drawCirclePoints(PolygonSpriteBatch batch, int centerX, int centerY, int x, int y, ColorRGBA color) { drawPoint(batch, centerX + x, centerY + y, color); drawPoint(batch, centerX - x, centerY + y, color); drawPoint(batch, centerX + x, centerY - y, color); drawPoint(batch, centerX - x, centerY - y, color); drawPoint(batch, centerX + y, centerY + x, color); drawPoint(batch, centerX - y, centerY + x, color); drawPoint(batch, centerX + y, centerY - x, color); drawPoint(batch, centerX - y, centerY - x, color); } The other way:
      public static void drawCircle(PolygonSpriteBatch target, Vector2 center, float radius, int lineWidth, int segments, int tintColorR, int tintColorG, int tintColorB, int tintColorA) { Vector2[] vertices = new Vector2[segments]; double increment = Math.PI * 2.0 / segments; double theta = 0.0; for (int i = 0; i < segments; i++) { vertices[i] = new Vector2((float) Math.cos(theta) * radius + center.x, (float) Math.sin(theta) * radius + center.y); theta += increment; } drawPolygon(target, vertices, lineWidth, segments, tintColorR, tintColorG, tintColorB, tintColorA); } In the render loop:
      polygonSpriteBatch.begin(); Bitmap.drawBresenhamCircle(polygonSpriteBatch,500,300,200,ColorRGBA.Blue); Bitmap.drawCircle(polygonSpriteBatch,new Vector2(500,300),200,5,50,255,0,0,255); polygonSpriteBatch.end(); I am trying to choose one of them. So I thought that I should go with the one that does not involve heavy calculations and is efficient and faster.  It is said that the use of floating point numbers , trigonometric operations etc. slows down things a bit.  What do you think would be the best method to use?  When I compared the code by observing the time taken by the flow from start of the method to the end, it shows that the second one is faster. (I think I am doing something wrong here ).
      Please help!  
      Thank you.  
    • By ethancodes
      I'm working on an endless wave-based arkanoid/space invaders style hybrid. Bricks spawn above the screen and move down line by line. You must destroy all bricks before they hit the bottom of the screen. There will be multiple types of bricks and random power-up spawns. Currently I am just using a simple Log function that takes in the current wave as a parameter. This works to increase the number of bricks spawned each wave, but I want to find a way to make this much more complicated. Here is a list of everything that should be effected by the increase in difficulty:
      1. Number of bricks
      2. Types of bricks (1 hit bricks, 2 hit bricks, 3 hit bricks, etc.) 
      3. Speed that the bricks move down the screen
      4. How often power-ups spawn
      The biggest problem here is that I can't just increase all of these with each new wave. If I did that, it would quickly become far to difficult. What I would like is an algorithm that gives some amount of variance in the increase between all 4 of these. Say one wave we put 60% of the increase to number of bricks, 20% increase to power-up spawns, 10% to types of bricks and 10% to speed of bricks. But on the next wave those percentages are all moved around and we now have say 105% to work with so the overall difficulty has increased as well. The different types of bricks need to also change to the point where if someone has made it to a certain wave, such as wave 50 for example, there are no longer any 1 hit bricks. We now would have just 2-4 hit bricks, and if they are crazy good and make it all the way to round 100, Now it's just 3-5 hit bricks, etc. 
      If anybody has any good ideas or suggestions on this, I'd appreciate anything you've got! Thanks!
    • By fazook
      Hi, guys!
      I have a rather abstract question, because I don't know which side to approach to its solution. So, I would appreciate any information.
      I have a task to create a simple game that generates floor plans and I following by this perfect algorithm (https://www.hindawi.com/journals/ijcgt/2010/624817/). At the moment I use squarified treemaps (http://www.win.tue.nl/~vanwijk/stm.pdf) and here no problems. I create nested array in which elements are rooms with size. Problems starts when I trying to represent generated "rooms" as edges and vertexes (a, b, c, d steps in attached picture) That representation can give me access to this elements as special "entities" in future game versions.
      I don't have skills in graphs (and do I need graphs?) and at the moment totally stucked at this step. How can I represent room walls as trees (or graphs?) at this step? Calculate size of squares (rooms) and convert sides to a vectors? Then in loop find shared vectors (same position by "x" or "y") and determine them as shared walls? The instinct tells me that there exist more elegant and efficient ways.
      Anyway, thanks for any information about this.

    • By Januario
      Hey guys!,
      So, I'm basically working on an explorer right now.
      It should, as the name suggests, explore the entire thing, the most efficient way possible.
      Your character has vision around you, of, 10x10. The map is much bigger, 100x100. However, it can't just go straight from a corner to another, because: The tiles can be an occupied, or un-occupied one. You can add weights to the tiles, so feel free to use this in your advantage (let's say, adding an extra weight to a visited tile so you can compare visited against non-visited ones). You can use the Pathfinder I'm using, based on the A* algorithm. So, I could be wrong, but by basic logic, I assumed that the "fastest way" to explore the entire thing, is answering the question "What is the nearest tile that I can walk in, that is not occupied and that can reveal as much fog-of-war (unvisited tile) as possible?"...
      My questions are:
      1) Is my question correct? is that really the best way to explore the entire map? 2) If so, what's the best way to know "which is the tile that could reveal the most fog of war"? Once I get the tile that reveals the most fog of war possible, then I just throw the pathfinder to it.
      But I'm having problems doing a good way to achieve that :'( 
      I hope you guys can help me on this one! 
      Thank you
    • By Scouting Ninja
      So what is up? What did I miss?
      I finally get my PC working and am bombarded with emails asking about marching cubes. Get on Gamedev.net and it's even here people are researching marching cubes. All of the gaming forums is a buzz with players theories on how marching cubes work, developers looking for teams to build a marching cube games.
      So why the spike? Reminds me of when Minecraft released.
  • Advertisement
  • Advertisement

Recommended Posts

Hello!

I was looking for a data-structure that is meant to handle sorting of 3d-objects, where every object, within trees or child trees, will potentially move/change their position, hence no static objects.

I am mainly curious if there is anything similar to an octree with a cheap update-complexity, because updating one element takes quite some iterations, e.g. recursively entering parent octrees, checking whether they fit in them or not...

I considered to roll out a 3d spatial hashing instead, as octrees' precision seems quite unimportant for my project as well. It would seem to be easier to update compared than an octree.

Why do I worry about performance? I really just would like to use the semantically most fitting structure. I often hear, quad- and octrees shine with static objects, because they allow a high precision via their branching of smaller trees within each tree. On the other hand, I totally do not need this, there is no complex collider either, just cubes.

I might be totally wrong on my performance-observations, though!

Summing it up, what would you recommend/use for a 3d-world with simple cube-colliders where every object is dynamic?

Thanks for your time!

Edit: Fixed terribly screwed sentences that were not even complete, sorry!

Edited by Angelic Ice

Share this post


Link to post
Share on other sites
Advertisement

Maybe you could sort by Morton Code?

From that nearby objects can be found without the need for a hierarchy by iterating the list in both directions until stuff is too far away.

Share this post


Link to post
Share on other sites

I'm also not an expert on this, but I've seen tutorials that teach you not to update the tree (octree, bsp tree, whatever), but to clear it out and build a new tree, every frame. While that is expensive, it's less expensive than re-sorting  to update an existing tree, and it's guaranteed to give you the correct results to render in any given frame.

Edited by masskonfuzion

Share this post


Link to post
Share on other sites
25 minutes ago, masskonfuzion said:

I'm also not an expert on this, but I've seen tutorials that teach you not to update the tree (octree, bsp tree, whatever), but to clear it out and build a new tree, every frame. While that is expensive, it's less expensive than re-sorting  to update an existing tree, and it's guaranteed to give you the correct results to render in any given frame.

This depends on how you store a tree in memory (all children in order vs. a pointer to the next child), what kind of tree you use, how your dynamic / static object count ratio is ,etc. Updating trees can be fast and good, e.g. octree for collision detecten if the tree does not change much from frame to frame. (But in general i agree)

You can also use two seperate trees for static world / dynamic objects (in case of BVH just put both under the root node and done), so you only rebuild for dynamic objects.

Using BVH you can also only rebuild the top levels of the tree and just refit the bottom levels bounding volumes (makes sense if you have large static but moving structures like spaceships).

7 hours ago, Angelic Ice said:

I was looking for a data-structure that is meant to handle partial spatial sorting of 3d-objects, where every object, within trees or child trees, will potentially

The sentence is not finished, being confused...

 

7 hours ago, Angelic Ice said:

Summing it up, what would you recommend/use for a 3d-world with simple cubes-colliders where every object is capable of moving but also to be expect to move?

You mean expected NOT to move? more confusing... :)

Are all cubes the same size? Game like Minecraft? You want collision detection or something else?

Share this post


Link to post
Share on other sites
36 minutes ago, JoeJ said:

The sentence is not finished, being confused...

Thanks for pointing out, I fixed it!

36 minutes ago, JoeJ said:

You mean expected NOT to move? more confusing... :)

Fixed this as well!

37 minutes ago, JoeJ said:

Are all cubes the same size? Game like Minecraft? You want collision detection or something else?

The gameplay is surely nowhere like Minecraft but the collision-world could be. Not all cubes have the same size, because terrain has a different cube-size compared to the player.

I want collision-detection and gravity-detection, which is pretty much just collision-detection on the height-axis.

Share this post


Link to post
Share on other sites

There was a thread about spatial hashing recently: https://www.gamedev.net/forums/topic/689399-spatial-hashing/

Personally i'd start with a BVH (AFAIK most if not all physics engines use BVH now), and rebuild it every frame.

The fastest way to build is to run over all current objects to get the bounding box, then use the box center to sort the objects to the 8 resulting subspaces (child nodes) from that.

This gives not the best tree but quality does matter less than building time - usually.

Should be almost as easy to implement than a regular grid.

Edited by JoeJ

Share this post


Link to post
Share on other sites

Deleting a tree data-structure just to rebuild it, with e.g. 200 objects every cycle, shall be more efficient than updating one or two moving objects? Wow! Really have to try that. Sounds like a massive amount of overhead per cycle. Wouldn't deleting an object that just moved and inserting them be a solution too? Though, I could see this become less efficient if every objects out of 200 would be moving at once, but that would never be the case on my end.

12 hours ago, JoeJ said:

Personally i'd start with a BVH (AFAIK most if not all physics engines use BVH now), and rebuild it every frame.

Thanks, I will totally read about BVHs!

 

Edited by Angelic Ice

Share this post


Link to post
Share on other sites
5 hours ago, Angelic Ice said:

Deleting a tree data-structure just to rebuild it, with e.g. 200 objects every cycle, shall be more efficient than updating one or two moving objects? Wow! Really have to try that. Sounds like a massive amount of overhead per cycle. Wouldn't deleting an object that just moved and inserting them be a solution too? Though, I could see this become less efficient if every objects out of 200 would be moving at once, but that would never be the case on my end.

You did not tell those numbers, i assumed most of the world would move.

But first: 200 objects is not much - you wont see much difference. BVH build should take something like 0.1ms on one core (wild guess).

You don't need to delete if you rebuild. You did not intend to allocate each node with new, did you? This would be horribly slow. So slow that i did not try this again the last 10 years - maybe memory allocation is less expensive today, but i doupt it. Just preallocate enough memory and write your nodes in cache friendly order. (I also never use recursive function calls to build or traverse a tree - this has not only an additional cost, it also prevents you from understanding what happens. Better to use another preallocated memory  for stack, queue or however you call it. But that's optional. I have to say that most tutorials fail to show this things. They tell you how it works but not how to do it efficiently.)

For a 200 vs 2 objects ratio you're right and updating the tree should be faster than rebuilding. But you loose the property that you can write all child nodes in order (instead you get fragmented memory), and this will slow traversal down. You could traverse the result once to sort for memory order, but that's the same cost as a complete rebuild. Also you have to consider always the worst case, which is a larger number of moving objects.

You would need to implement multiple methods to profile for the fastest, but usually whatever you pick initially is fast enough. For 200 objects you don't need to worry anyways. Rebuild is easier to implement than update, and BVH is easier and more flexible than octree, so it's a good start and probably you'll keep it.

 

 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


  • Advertisement