Jump to content
  • Advertisement

Delpee

Member
  • Content Count

    9
  • Joined

  • Last visited

Community Reputation

109 Neutral

About Delpee

  • Rank
    Newbie
  1. Delpee

    A* speed

    Awesome, I'll await the post ;-).
  2. Delpee

    A* speed

    I would love to see it, even just as a way to see the differences! Which sorting mechanism did it use?
  3. Delpee

    A* speed

    What I do is get a DateTime.Now before calling the algorithm-function and directly after the function returns the path I take the difference between the old DateTime.Now and the current one. In this way I exclude any other code from the time tracking.
  4. Delpee

    A* speed

    Thanks smr for your response. I think it mainly has to do with the iteration of my closed list. My heuristic is allready calculated Manhattan style. Maybe I could improve the open list a bit, but I surely should get rid of the closed one as everyone is telling me ;).
  5. Delpee

    A* speed

    I just tested my implementation on a 100x100 randomly generated world (1 in 10 tiles are blocked). After about a second I consistently get a Stack Overflow error. Is this because I use lists to store my closed nodes?
  6. Delpee

    A* speed

    71ms is indeed a long time. I'm not realy sure why, but sometimes the calc-time spikes. Could have something to do with with some other program running at the same time (maybe the snipping tool I used for screenshot?). I'm not realy worrying as the average is way lower. Sometimes it's also way lower then average. Good tip, will do! I will post the results. I just see the first picture of the stresstest isn't right, replacing it right now!
  7. Delpee

    A* speed

    That is indeed something to think about. In practice though the world is probably not empty (otherwise there is no point to A*), so I don't know if it would make that much of a difference though.
  8. Delpee

    A* speed

    Hello GameDevs, I recently did an implementation of the A* algorithm. I'm pretty satisfied with the result as this is my first real 'adventure' in the area of AI (I have been programming for about 7 years). The implementation delivers results pretty quick and accurate. While implementing a question came to mind, how fast is fast? Here are some images of the implementation in practice: Agent moving a long distance Agent moving through a maze Two videos showing the implementation in practice: Video 1 Video 2 To see how fast my implementation worked I did a stresstest. I made the program calculate thousands of paths from random startpoints to random endpoints in my grid. I did this in an empty grid of 40 by 23, an obstacle-filled grid of 40 by 23 and an empty grid of 100 by 100. These are the results: 40 by 23, no obstacles 100 by 100, no obstacles 40 by 23, difficult terrain Note that I'm mainly concerned about the average calculation time, as you can see, at the 40 by 23 grid with a difficult terrain there is an average calculation time of about 8ms. Also note that I don't have diagonal search, only horizontal and vertical. My question to the GameDev boards; Is this an acceptable speed, can it be categorized as fast, or slow? Discuss... Thanks in advance, Yuri van Geffen
  9. Delpee

    line based pathfinding?

    Like JTippetts said, just keep checking for a node in the path which can be reached directly (straight line) and has the lowest cost of the directly reachable nodes. Make sure to check once in a while if the node is still reachable (directly) if you have moving inpenetrable though!
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!