• Advertisement
  • Popular Tags

  • Popular Now

  • Advertisement
  • Similar Content

    • 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 akshayMore
      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) { drawBresenhamCircle(batch, centerX, centerY, x, y, color); if (d <= 0) { d = d + 4 * x + 6; } else { y--; d = d + 4 * (x - y) + 10; } x++; //drawBresenhamCircle(batch,centerX,centerY,x,y,color); } } private static void drawBresenhamCircle(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 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

Pathfinding Eikonal vs Grass Fire Algorithm

Recommended Posts

Hi, I was reading Game AI Pro how they implemented Supreme Commander path finding and came to one question.

For the integration of cost field they are using Eikonal equation for traversing the areas.
They recommended Fast Iterative Method and it's parallel version for solving this equation.
However in all basic tutorials of flow field navigation that I found  for integrating of the cost field is used simple grass/brush fire algorithm.

My question is what would be the difference if they used in the game just grass fire algorithm?

I guess the reason was some quality/performance trade of.
Fortunately the Fast Iterative Method is very easy to implement so I can compare the performance, but what I don't understand is, what is the "quality" benefit.

Edited by gamer9xxx

Share this post

Link to post
Share on other sites
On 15/7/2017 at 0:10 PM, gamer9xxx said:

For the integration of cost field they are using Eikonal equation for traversing the areas.

No, the eikonal equation defines what is a shortest path. "Traversing the areas" is what algorithms that compute solutions of the eikonal equation, i.e. shortest paths, need to do somehow.  In the case of chapter 23 of Game AI Pro:


We are now ready for cost field integration. As with the LOS pass, we start with the active
wave front list. This active wave front comes from the list of “Wave Front Blocked” loca-
tions from the previous LOS pass. In this way we only integrate locations that are not
visible from the goal.
We integrate this wave front out until it stops moving by hitting a wall or a sector
border. At each grid location we compute the integrated cost by adding the cheapest cost
field and integrated cost field’s up, down, left, or right neighbors together. Then repeat this
Eikonal equation process again and again, moving the wave front outward toward each
location’s un-integrated, non-walled neighbors.

Maintaining a list of active wavefront cells looks definitely like a "brushfire" algorithm.

Are you confusing this basic building block of multiple source/single destination grid-based pathfinding with the full pathfinding solution described in the book (tile-based architecture, portals, caching, LOS special case, specific flags and data structures, etc.)?

Share this post

Link to post
Share on other sites

Hi, thx for the explanation, yes it was just a confusion what eikonal equation is, since they added the whitepaper that describes how to solve it with the Fast Iterative Method, but apparently they didn't use it at all, but what they wrote in your quoted part, it's simple "brushfire" alg.

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