www.jpct.net
jPCT - a 3d engine for Java => Projects => Topic started by: raft on May 25, 2007, 10:36:15 am
-
welcome jKilavuz (http://www.jkilavuz.com/), 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 (http://www.gamasutra.com/features/20020405/smith_pfv.htm) 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 (http://www.jkilavuz.com/jws/qdemo.jnlp) 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
(http://img157.imageshack.us/img157/8393/topviewke8.png)
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
(http://img265.imageshack.us/img265/4803/gridpanelpw4.png)
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
-
Daaaaaaaaaaaaaaaaaamn that's nice man! Nice implementation also! Had running the guy around with no problem! Good job :D.
-
That is really great Raft! Nicely done! You should call it A* 3D since it handles elevations.
-
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.
-
thanks folks, i'm glad you liked it ;D
-
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.
-
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 ::)
-
for the name, ehe, it's my curse i'm afraid.
The name is great. I really like it despite of the funny sounding.
-
That is fantastic. Well done! It is extremely effective!
-
Fantastic stuff.
-
here we go ;D the first publicly available version of jKilavuz (http://www.jkilavuz.com/downloads/jkilavuz-0.9-beta.zip).
the site and documentation is not quite ready and starting from saturday i will be away from keyboard for about a week (holidaaayyy here (http://www.butterflyvalley.com/valley.htm) :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
-
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!
-
Nice demos. I wish you a happy and fulfilling holiday. Don't forget to post a picture... ;)
-
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
-
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
(http://img501.imageshack.us/img501/6492/aysenilehakantatilde17mj9.jpg)
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
(http://img48.imageshack.us/img48/5118/aysenhakantatilde59ef0.jpg)
r a f t
-
Ahhh...mountains! Are they actually accessible?
-
if you ask for rules preventing climbing, as far as i know there is no such rule. i'm not a climber but i guess one would require equipments to climb there as they're pretty steep. one can go up by foot a bit around the waterfall and there are ropes left by ones who climbed there before. i dont know what's upstairs as i went only till ropes ;)
-
i've just released the first public version of jKilavuz with a licensing schema. source code is not included in any of the licenses. no forum at the site at the moment but a google group (http://groups.google.com/group/jkilavuz) for communication. anyone interested in jKilavuz is welcome
http://www.jkilavuz.com
-
I've updated the projects page to link to the new homepage (which looks very nice and clean btw).
-
thanks :D
-
Can this be used in order to find the best or at least a good route once getting the necesay information about the streets?
I am still thinking on use jpct for a cartography system, so I want to trace a route between 2 gps points!
I will have a vectorial map for the roads, but there might move not only (up/down, right or left) but the streets may have different shapes or directions.
-
yes, you can use jKilavuz for a such a purpose.
a) if you have a 3d model of your map, you can directly use jKilavuz
b) if you dont, implement your own StepChecker (http://www.jkilavuz.com/doc/api/raft/kilavuz/grid/StepChecker.html) based on your map data
paths generated by jKilavuz arent restricted to cardinal directions, so different shapes wont be a problem. jKilavuz cannot always guarantee shortest paths (as it uses a hierarchical approach) but the results are pretty good and sufficient.
r a f t
-
ok thanks, once I implemented backtracking to find chesse inside a maze and worked but path the mouse moved wasnt optimal, in fact on some cases was the further one!
-
i have made a sample and simple StepChecker implementation based on java 2d.
this is how the simple city looks. red line stands for city borders and filled shapes are obstacles (buildings)
(http://img520.imageshack.us/img520/4446/citybk6.png)
this is the grid created from the city and a found path. more precision can be supplied by decreasing the cell size but requires a license
(http://img526.imageshack.us/img526/2783/gridoi4.png)
here is the code of AwtStepChecker (http://www.aptalkarga.com/download/AwtStepChecker.java).
r a f t
-
sorry this is not related to jPCT in anyway but i found it interesting :-\
nowadays a puzzle is traveling with email: take a car out of a maze where turn directions at corners are restricted and predefined. below is an image of the puzzle:
(http://img249.imageshack.us/img249/66/carpuzzlexo1.png)
a copy of the original interactive power point version of car puzzle can be found here (http://www.jkilavuz.com/downloads/car_puzzle.pps)
and this is an A* based solution of puzzle (http://www.jkilavuz.com/downloads/CarPuzzle.java) based on jKilavuz's generic A* implementation ;)
r a f t
-
Does it work?
(http://www.jpct.net/img/jk_add.jpg)
??? ;D
-
ehm, i'm caught ;D
yes, it does somehow work indeed. jKilavuz site receives some visits from that adds costing 1$ or less daily. i'm just trying to make people know about jKilavuz
it took your attraction for instance 8)
-
Hey, this is pretty cool. I play around with adventure games and it would work great. I'd have to use the free version, though. I'm kind of low on funds. ;D
-
thank you, i'm glad you liked it ;D
you can increase cell width to cover a larger area in freeware version, but of course that will decrease precision. you may also wish to join the google group: http://groups.google.com/group/jkilavuz although there is no activity :/
feel free to ask anything ;)
-
May I use it for a pac man game???? I tried using backtracking but the ghost were too stupid
-
the PacMan levels are flat and grid so you dont need jKilavuz for it IMHO. but you can use jKilavuz's A* implementation for sure
-
A few years ago I studied for cooperative pathfinding and implemented a prototype based on David Silver's academic paper. It's called WHCA* (Windowed Hierarchical Cooperative AStar). My implementation was incomplete and far from perfect but functional. Yesterday my Google alert notified me about a post which is asking for sample code for cooperative pathfinding. I've published it here as it is http://www.jkilavuz.com/whca/, hoping it may help someone.
Seems as David's original paper is not where it should be, but there are many copies on the web. I had included my copy in my page. There is also a youtube video showing demo running.
A couple of notes (if I remember correctly)
* "Normal" A* can tell you if there is no solution but WHCA* cannot (at least as it is)
* With normal A* you get unnatural and unaesthetic paths unless you do some post processing. Same applies for WHCA*.
* The degree of cooperation depends on depth (of time) of search. If two units are blocked in a narrow corridor of X units of length, search depth should be at least X+1 to solve this situation.
* As expected there is a trade off here: The deeper the search the more likely it should solve blockages but the more expensive it will be.
* As the name suggests, the search for each unit is windowed. Each unit searches for a partial route to its destination at regular intervals. This sometimes results in -seemingly unnecessary- waits.
r a f t