• Advertisement


  • Content count

  • Joined

  • Last visited

Community Reputation

536 Good

About jack_1313

  • Rank
    Advanced Member
  1. Hi Jack, Alvaro's solution won't well work for a robust navigation mesh system. Please see my response in this thread. In it, I discuss the problems introduced by accounting for agents of different sizes as well as how to resolve them.
  2. Navmesh without agent radius offsets

    Hi DrEvil, Sorry that it’s taken me a little while to get back to your post/PM. I’m really under the pump with work at the moment. To account for agents with varying sizes, we need to solve two problems: 1. We need to account for agent size when running our A* algorithm on the navigation mesh to find the list of nodes (be they triangles or convex polygons) which will contain the final path. That is to say, we can't send agents through gaps that are too small for them. 2. We need to account for agent size when “funnelling” through the list of nodes returned by our A* search to obtain the actual shortest path. For problem #1, please see my full description and solution in this post from 2008. You will see that for each node, it is necessary to store a separate size restriction value for every edge-pair combination that an agent could enter and leave from. If our nodes are triangles, this means each one must store three separate widths. If we allow other kinds of convex polygons, then the number of widths each node must store will be equal to the sum of all integers from 1 to (number_of_neighbours – 1), if my brain is working correctly at the moment. We would need to come up with an equation to reference the right value from a node’s array of stored widths given an entry edge and an exit edge – this should be fairly trivial. For problem #2, please see my solution in this post from 2009, as well as my other contributions in the same thread. The linked post explains (my version of) the funnel algorithm and then explains the modifications that you need to make to account for agent size, providing pseudo code at both stages. Just let me know if you have any questions. On a side note, I obviously don’t think that the traditional solution of expanding and bevelling the base navigation mesh to account for agent size is very elegant. Apart from necessitating a new mesh for each possible agent size, it also increases the complexity of the navigation mesh at every concave feature. For fast pathfinding, we want to reduce the number of nodes that need to be searched, not increase it.
  3. Hi Gamedev.net! Years ago, I was an active member here and a very enthusiastic game programmer. For the better or worse, life took me in a different direction. I turned away from game programming and have spent the last so-many years studying history and foreign language. It occurred to me that I have, sitting idle on my hard disc, a fast and robust navigation mesh / path finding implementation based loosely on the Douglas Demyen Triangle-Reduced A* thesis (of which seems to have disappeared from the internet – only the shorter journal article is now available). It was part of a game I was working on years ago, was rewritten from scratch on at least one occasion. Rather than let that work go to waste, I thought I might turn it into a stand-alone C++ library that would be free for non-commercial use. Features: * Automated construction of navigation mesh (uses Triangle triangulation library). * Speed. The implementation is fast, primarily, because only triangles with three neighbours (“keynodes”) are included in the A* search. All other triangles are collapsed into “corridors” and skipped over. In most environments, keynodes account for 1/4 to 1/3 of all triangles in the navigation mesh. * A single navigation mesh is used to find paths for agents of any size – no need for duplicate navigation meshes. * It’s paired with a kd-tree system that has some bonus features that could be useful (very fast visibility + swept circle checks against navigation mesh etc). Shortcomings: * It’s simple-2D only – does not support overlapping areas or varying-cost terrain types, though the former could probably be implemented without a huge effort. * The navigation mesh cannot be dynamically updated. * I doubt I would be able to spend a lot of time developing it further. Here’s a few screenshots of the implementation finding some very long paths. Time estimates were recorded on my laptop – an Intel i5-2450 2.50GHz processor – in a standard Windows 7 environment, and are the average of 10 000 queries.   Search time: 0.041ms and 0.036ms. Navmesh: 772 triangles, 255 of which are keynodes (pink).   Search time: 0.039ms and 0.025ms. Navmesh: 820 triangles, 251 of which are keynodes.   Search time: 0.069ms and 0.056ms. Navmesh: 1213 triangles, 366 of which are keynodes.   Varying agent sizes pose no problem. Search time for each path: in the range of 0.006ms. It looks like the need for such a library has lessened due to the appearance of Detour, which didn’t exist when I developed it. In short, I’m just wondering if there would be any interest in this project? I can only really justify putting time into it if it looks like there might be some interest/communal benefit.   Thanks for reading!
  4. 2D Top-down multiplayer-style shooter

    Hi Mybowlcut, thanks for playing. The camera actually does automatically follow the player after he dies. It just takes a few seconds to respawn, which is supposed to be punishment for dieing. The game usually has sound, at least for testing purposes. I just had to take them out before posting because they are all borrowed from Soldat. The AI has probably been the largest part of development. Although I started with multiplayer in mind, the game quickly turned into an arena for me to experiment with AI techniques. I'm pretty happy with the cat-and-mouse style combat that has been the result.
  5. Here’s a project that has been going on/off/slowly for more than five years. Unfortunately, since my life is now occupied by university studies in a non-related field, there’s not much time or motivation to finish this game. Thus, I thought I’d post the current build here on Gamedev on the chance that others might enjoy what is done or even motivate me to begin working on it again over the holiday break. It's a 2D top-down team-based shooter. This version is single-player only and features one capture-the-flag map. The screenshots tell the story: Controls are mouse for aiming and shooting and WSAD for movement. F changes weapon. Pressing N will allow you to cycle through viewing the computer players with some cryptic on-screen information about their AI. Download here. Download size is negligible (362kb). RAR format. Thanks for reading/playing! Jackson Allan
  6. How much do you trust Wikipedia?

    Quote:Original post by zyrolasting This is obvious now, but just to reiterate, some academic facilities suspect that Wikipedia is unreliable due to the fact that articles can be edited publically. In terms of academics, whether the information on Wikipedia is accurate or not is a secondary issue. You've already noted the more important issue: Quote: I suppose the real issue (again, probably just stating the obvious) is that people believe that the information on Wikipedia can change at any moment This isn't just something that "people believe," it is a true fact. If you are writing a research paper or any high level of academic work you are expected to cite your sources of information so that readers can trace that information to its sources. Regardless of its perceived quality, you can't do this with Wikipedia because the information you cite might not even exist the next day. Thus, it doesn't matter if 50%, 90% or even 100% of editors are considered "competent." For academic purposes, Wikipedia can't be used other than on an informal basis. The sources that Wikipedia cites, however, are often static texts - thus your school's encouragement for students to use Wikipedia as a "shortcut", or gateway to relevant texts on whatever subject. Quote: Isn't treating work like a "Links" page to more "trusted" (read: relevant) material kind of an eff-yew to competent contributors? Not really, for the reasons explained above. You'd be more interested in the "References" section, though. It's normally not difficult to tell which texts are things that you can include in your papers.
  7. Are you sure you weren't portraying the image of a victim? If you're a pussy, thieves like you. So start being more mean or stop complaining.
  8. The wildest posts on GD.net?

    Quote:Original post by Alpha_ProgDes This is currently my all time favorite: Quote: My suggestion is that Islam is a greater threat than some possibilities of WMD developments. A pre-emptive nuclear strike on Mecca and Medina would serve the West well in seeding deep doubt in the devout Islamists--if the holy sites go up in mushroom clouds, that would beg the question: "Where is your Allah now?" I already pointed out the insanity of this little nugget in the thread that it came from. But it does surprise me that, on Gamedev.net, clearly advocating genocide is not an offense even worthy of an official warning, whereas other comparatively minor offense, such as arguing with moderators or insulting other members, would get someone suspended or banned. Edit: Oops! He did get a warning for it. Thanks for correcting that one Hodgeman. On a lighter note, there have been some pretty crazy threads in previous years. Two of my all-time favorites were the iPod-Girl-present-giving fiasco and the notorious MMO Hockey Game thread. [Edited by - jack_1313 on September 15, 2010 11:57:59 PM]
  9. I'm sorry for 9/11...

    Quote:Original post by Prune My suggestion is that Islam is a greater threat than some possibilities of WMD developments. A pre-emptive nuclear strike on Mecca and Medina would serve the West well in seeding deep doubt in the devout Islamists--if the holy sites go up in mushroom clouds, that would beg the question: "Where is your Allah now?" This was the point where I realized that you're just insane.
  10. Quote:Original post by owl First of all, I'd like to know if the translation is correct. I found no significant inaccuracies in the translation. In my opinion, you can tell that the host thinks that Dr Sharif is a total nut-case.
  11. What's your favorite song(s)?

    Nice to see a lot of metal representation! As for me: After Forever: My Pledge of Allegiance I Kamelot: March of Mephisto Epica: Cry For The Moon Pity Australia doesn't exist as far as most metal acts are concerned.
  12. Pictures of YOU!

    Quote:Original post by ukdeveloper Me, after a few pints. Me and a few friends.
  13. Pictures of YOU!

    Here's one taken recently. I think I look rather dashing, wouldn't you say?
  14. Fair Dinkum!

    I thought Australian slang was grossly exaggerated in media as well, until I met two girls from Queensland. I mean, fair dinkum mate! It was like I was speaking to the crocodile hunter himself!
  15. Problem with Funnel Algorithm

    Quote:Original post by sybixsus I think I should be resetting the feelers right back to the apex at that point, as they would be at the start point, and I think I'm not doing that correctly somehow. If you're following this explanation and implementation of the funnel algorithm, then you should definitely do that. But I should verify: Demyen, the most detailed explanation I know, does the whole thing a bit differently (and quite possibly more efficiently). You’d need to consult his material for information.
  • Advertisement