Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 28 Jun 2003
Offline Last Active Mar 24 2014 08:30 AM

Topics I've Started

Interest in a (TR)A* Navigation mesh / Pathfinding Library?

18 April 2013 - 12:40 PM

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.

* 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).

* 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!

2D Top-down multiplayer-style shooter

05 December 2010 - 02:43 PM

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

Can't reply

07 January 2010 - 09:23 PM

Hello. Does anyone know why I might be unable to reply to any threads using either Google Chrome OR Internet Explorer 6.0, where I have not previously had problems? Why I try to post my reply the site eventually times out. Is anyone else experiencing this unusual problem? Also, if I moderator could please delete my other thread, 'test,' I would be grateful. I am unable to do so myself and also will not be able to respond to this tread. Thanks, Jackson Allan Edit: It seems I can create topics and edit posts, but not post replies. EDIT by Evil Steve: Nobody can post replies at the moment, the forums seem to be temporarily broken. I'm also unable to delete your other thread at the moment, but I seem to be able to edit posts... [Edited by - Evil Steve on January 8, 2010 4:11:54 AM]

Inheritance and duplicating items on an STL vector

18 November 2009 - 02:51 PM

Hello. I need to make a duplicate of an instance of a class which is held on an STL vector and put it onto another STL vector. The class inherits from a base class which is used when declaring the vectors:
std::vector<Maneuver*> maneuvers;								
std::vector<Maneuver*> requestedmaneuvers;

Maneuver is the base class of which several variants are derived from, and then added to these two lists like such:
maneuvers.push_back( new AIManeuverFlank ); 

To copy one of the instances on maneuvers vector to the requestedmaneuvers vector, I do this:
BYTE * temp = new BYTE[ maneuvers[ i ]->GetSize() ];
memcpy( temp, maneuvers[ i ], maneuvers[ i ]->GetSize() );
requestedmaneuvers.push_back( (Maneuver*) temp ); 

GetSize() gives the size of the derived class, because sizeof( *maneuvers[ i ] ) seems to return the size of the base class only. Thus far this works ok but seems sloppy. My question is whether this is acceptable practice, or is there a simpler method to perform this copy? I don’t need to worry about any dynamic containers that might be members either the base or derived classes. Thanks for reading, Jackson Allan

Finding coordinates of unkown point in right angle triangle

14 February 2007 - 10:21 PM

Hello. I’m trying to find the coordinates of an unknown point © in a right angled triangle. Allow me to attempt to demonstrate:
                          _ B
                     __*** |
            AB__***        |
        __***              |BC
  __***                   _|
A                           C?

I need to find C given A, B, AB and BC

I know the points A and B and therefore know the length of the side connecting them (AB). I also know the length of BC and that there is a right angle at point C. Finding the length of AC using Pythagoras and the unknown angles using trigonometry is trivial. The problem is that I do not know how to find the coordinates of point C efficiently. I already know I can test a circle centred on the midpoint of AB, diameter equal to that sides length, with a circle centred on B, radius equal to the length of BC. I’d prefer to avoid doing this though as it seems like an overkill, and I am hoping for the fastest method as this calculation will be a vital part of a path finding routine and will be called upon hundreds of times in one search (the true problem is finding a tangent to a circle that runs through a given point). Thanks for any help, Jackson Allan.