jKilavuz: a guide in the polygon soup

[raft]

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 t

edit: added a link to home site and moved the demo link to home too

[Remo]

Daaaaaaaaaaaaaaaaaamn that's nice man! Nice implementation also! Had running the guy around with no problem! Good job .

[ToddMcF2002]

That is really great Raft!  Nicely done!  You should call it A* 3D  since it handles elevations.

[EgonOlsen]

Extremely cool!!! I tried to fool it by clicking on an unreachable (or so i thought) platform and he walked towards it and jumped onto it. Amazing work. There has to be a market for something like this.

[raft]

thanks folks, i'm glad you liked it 

[EgonOlsen]

I've added Kilavuz to the projects page.

BTW: The name has a funny sounding in german...it sounds like Killerwutz, which would be a deadly female pig in some idioms.

[raft]

thanks, so this is a fast start

for the name, ehe, it's my curse i'm afraid. for instance raft doesnt have anything to do with the word raft (boat) in english 

[EgonOlsen]

for the name, ehe, it's my curse i'm afraid.

The name is great. I really like it despite of the funny sounding.

[cyberkilla]

That is fantastic. Well done! It is extremely effective!

[eye1]

Fantastic stuff.

[raft]

here we go the first publicly available version of jKilavuz.

the site and documentation is not quite ready and starting from saturday i will be away from keyboard for about a week  (holidaaayyy here :p), so i will not post anywhere else about kilavuz for now. the first version is only available for jPCT users  it contains the API, a tutorial, javadocs and two small samples to show what jKilavuz is about.

serve yourself

btw, while struggling to document kilavuz, i really appreciated once again Egon's effort to properly document jPCT.

r a f t

[ToddMcF2002]

Really impressive.  The demo's are really great!  I have to admit because of complexity I was going to avoid elevations for my ToEE RPG and implement regular 2D A* but now that this exists...

What is your distribution going to look like?  Will source be included with purchase like Torque?

Again, really impressive Raft!

[EgonOlsen]

Nice demos. I wish you a happy and fulfilling holiday. Don't forget to post a picture...

[raft]

thanks for the holiday you may be sure i'll do my best

i'm not sure about the distribution format. source may be included in a higher package but there's a problem: kilavuz uses of a lot of karga classes behind the scenes. so i dont know yet what to do about it

[raft]

so i'm back, and here are two photos as i promised:

this is the entrance of butterfly valley. if you like camping and nature i strongly recommend it. if you look for comfort it's certainly not for you the valley goes in for 2km or so and there is a waterfall at the end. there is no road (except an alley for goats) to butterfly valley and most probably will never be. the only transportation is by boats which makes it such a virgin. for instance electricity is generated by a generator


and this is a scene of ka$ from the nearby ka$ camping. again the nature is great but there is also comfort too. ka$ is one of my favorite places in turkey


r a f t