welcome
jKilavuz, a sister project of karga
for a couple of months i've been working on a pathfinding system for karga. i've read a lot, thought a lot and concluded in pathfinding is not that hard, hard part is collecting necessary data. i've barrowed the idea at the
great article at gamasutra. now it is already shaped and i'm happy with the results. here is how it works in short:
starting a from a set of points on ground, floodfills to 4 cardinal directions until all map is explored. this is our massive raw grid data consists of cells. it's a kind of 2d grid in 3d space which can take us up or down slopes, across bridges and over and under overpasses. we than analyze cells and collide them into freely traversable rectangular regions called sectors and portals between sectors. all the process is automized and quite time consuming. we have the option to intercept with sector creation and to create custom portals for elevators teleporters etc.
here is a demo for our old friend quake level of fps example. move camera freely with arrow keys, a, z, s, x. click anywhere around and the avatar will come. f to follow avatar and toggle free camera again. almost all places are reachable. although unlikely if stuck r to reset to start position. v to visualize path finding sectors. dont miss the elevator
it takes about 15 minutes to generate pathfind data on my 1.86 ghz notebook. there are a total of 384 sectors and 1348 portals. although the grid takes 5-6mb the runtime pathfinding information is only ~207k uncompressed
here are some key features and design goals:
* the pathfind algorithm is A*. it's a generic one not limited to kilavuz sectors
* minimum JRE version is 1.5
* kilavuz is targeted to java users not especially jPCT users. flood filling is plugable. there is a default implementation which uses jPCT's collision detection capabilities but it is not mandatory. the runtime only requires SimpleVector and Matrix classes to work. so any non-jPCT user can use kilavuz by simply transforming coordinates into his space
* all calculations are done in grid space. when executing path, coordinates are transformed back into world space. elevations are calculated by interpolation. the demo doesnt use any kind of collision detection but avatar nicely fits on ground almost all times
* users may intercept both with sector/portal creation and path exectution. the runtime supllies a small and limited set of classes to iterate over paths (either linear or curved) over time but anyone can use his own path execution system. the methods for converting between grid and world space provided. for special portals (like the elevator), the runtime uses factory interfaces to create relevant path segments. for example, this way one can plug actions like going somehere and calling the elevator by pressing a button
here is a shot from demo. top view with sectors visualized
and this is how our grid looks like. notice how the found path goes upstairs passing over itself. you can see the cells (the small circles), transitions between cells and sectors and portals here
although not certain, kilavuz will most likely be a commercial api with a limited freeware version. sorry i'm really broke nowadays :/
i will soon make a site for it when polished and documented the api
just for reference, kilavuz means guide in turkish
cheers
r a f tedit: added a link to home site and moved the demo link to home too