Author Topic: jKilavuz: a guide in the polygon soup  (Read 21657 times)

Offline raft

  • quad
  • ******
  • Posts: 1966
    • View Profile
    • http://www.aptalkarga.com
jKilavuz: a guide in the polygon soup
« on: May 25, 2007, 10:36:15 am »
welcome jKilavuz, a sister project of karga ;D

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
« Last Edit: June 01, 2007, 04:06:29 am by raft »

Offline Remo

  • int
  • **
  • Posts: 64
    • View Profile
    • http://www.opsdirector.com/3dart
Re: kilavuz: a guide in the polygon soup
« Reply #1 on: May 25, 2007, 11:54:22 am »
Daaaaaaaaaaaaaaaaaamn that's nice man! Nice implementation also! Had running the guy around with no problem! Good job :D.

Offline ToddMcF2002

  • long
  • ***
  • Posts: 103
    • View Profile
Re: kilavuz: a guide in the polygon soup
« Reply #2 on: May 25, 2007, 12:33:20 pm »
That is really great Raft!  Nicely done!  You should call it A* 3D  since it handles elevations.




Offline EgonOlsen

  • Administrator
  • quad
  • *****
  • Posts: 11745
    • View Profile
    • http://www.jpct.net
Re: kilavuz: a guide in the polygon soup
« Reply #3 on: May 25, 2007, 12:34:51 pm »
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.

Offline raft

  • quad
  • ******
  • Posts: 1966
    • View Profile
    • http://www.aptalkarga.com
Re: kilavuz: a guide in the polygon soup
« Reply #4 on: May 25, 2007, 01:36:25 pm »
thanks folks, i'm glad you liked it  ;D

Offline EgonOlsen

  • Administrator
  • quad
  • *****
  • Posts: 11745
    • View Profile
    • http://www.jpct.net
Re: kilavuz: a guide in the polygon soup
« Reply #5 on: May 25, 2007, 07:43:39 pm »
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.

Offline raft

  • quad
  • ******
  • Posts: 1966
    • View Profile
    • http://www.aptalkarga.com
Re: kilavuz: a guide in the polygon soup
« Reply #6 on: May 25, 2007, 08:24:01 pm »
thanks, so this is a fast start ;D

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  ::)

Offline EgonOlsen

  • Administrator
  • quad
  • *****
  • Posts: 11745
    • View Profile
    • http://www.jpct.net
Re: kilavuz: a guide in the polygon soup
« Reply #7 on: May 25, 2007, 09:00:06 pm »
for the name, ehe, it's my curse i'm afraid.
The name is great. I really like it despite of the funny sounding.

Offline cyberkilla

  • float
  • ****
  • Posts: 413
    • View Profile
    • http://futurerp.net
Re: kilavuz: a guide in the polygon soup
« Reply #8 on: May 25, 2007, 09:25:53 pm »
That is fantastic. Well done! It is extremely effective!
http://futurerp.net - Text Based MMORPG
http://beta.rpwar.com - 3D Isometric MMORPG

Offline eye1

  • int
  • **
  • Posts: 68
    • View Profile
Re: kilavuz: a guide in the polygon soup
« Reply #9 on: May 25, 2007, 11:05:58 pm »
Fantastic stuff.


Offline raft

  • quad
  • ******
  • Posts: 1966
    • View Profile
    • http://www.aptalkarga.com
Re: jKilavuz: a guide in the polygon soup
« Reply #10 on: June 01, 2007, 04:22:46 am »
here we go ;D 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

 

Offline ToddMcF2002

  • long
  • ***
  • Posts: 103
    • View Profile
Re: jKilavuz: a guide in the polygon soup
« Reply #11 on: June 01, 2007, 05:13:52 pm »
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!

Offline EgonOlsen

  • Administrator
  • quad
  • *****
  • Posts: 11745
    • View Profile
    • http://www.jpct.net
Re: jKilavuz: a guide in the polygon soup
« Reply #12 on: June 01, 2007, 06:44:20 pm »
Nice demos. I wish you a happy and fulfilling holiday. Don't forget to post a picture... ;)

Offline raft

  • quad
  • ******
  • Posts: 1966
    • View Profile
    • http://www.aptalkarga.com
Re: jKilavuz: a guide in the polygon soup
« Reply #13 on: June 01, 2007, 07:46:37 pm »
thanks ;D 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

Offline raft

  • quad
  • ******
  • Posts: 1966
    • View Profile
    • http://www.aptalkarga.com
Re: jKilavuz: a guide in the polygon soup
« Reply #14 on: June 11, 2007, 04:44:11 pm »
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