Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (487)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (552)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Pathfinding  (Read 4072 times)
0 Members and 1 Guest are viewing this topic.
Online kevglass

JGO Kernel


Medals: 158
Projects: 23
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Posted 2003-12-24 10:12:14 »

Well, Martian Madness has morphed into a sort of team based RTS and I've just started considering path finding. I have an free form map in which I can place obstacles.. any one have any useful links/info on how to perform path finding between two points..

And yes.. I'm just off to trawl google Wink

Kev

Offline zparticle

Senior Member




Thick As A Brick


« Reply #1 - Posted 2003-12-24 15:01:15 »

http://www.java-gaming.org/cgi-bin/JGNetForums/YaBB.cgi?board=share;action=display;num=1037669044

Offline Jeff

JGO Coder




Got any cats?


« Reply #2 - Posted 2003-12-24 17:46:38 »

There's also an A-star and i believa modified A-star that prefers interior paths (more natural looking)in Scroller.

But I'm not sure A-star is going to work for him if his map is truely free-form with no cellular structure at all.

Typically free-form environments are done with way-points.

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Online kevglass

JGO Kernel


Medals: 158
Projects: 23
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Reply #3 - Posted 2003-12-25 10:41:57 »

I'm afraid I couldn't gleen anything from the puppy games library AStar algorithm...

The map is fairly freeform there are screenshots here:

http://www.newdawnsoftware.com/martian/screenshots

Waypoints sounds like a lot of extra map design up front.

Kev

Offline Jeff

JGO Coder




Got any cats?


« Reply #4 - Posted 2003-12-25 19:26:00 »

Hm.,  This is a horizontal scroller it looks like,  Usually these don't
require much pathfinding.

What exactly are you trying to accomplish?

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Online kevglass

JGO Kernel


Medals: 158
Projects: 23
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Reply #5 - Posted 2003-12-25 19:57:37 »

Ah no, the later screenshots show what I'm trying to do now.. its a kinda psuedo-isometric rts style game now..

EDIT: would have probably been easier if I'd just posted the screenshot direct in the first place.. sorry about that: http://www.newdawnsoftware.com/martian/screenshots/241203_4.gif

Kev

Offline zparticle

Senior Member




Thick As A Brick


« Reply #6 - Posted 2003-12-26 12:33:05 »

I would think A-Star would be perfect for that kind of "map".

Online kevglass

JGO Kernel


Medals: 158
Projects: 23
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Reply #7 - Posted 2003-12-26 16:47:39 »

From what I understand (not much) about A-Star its based on building of graph of nodes representing the possible locations on the map. After that its just simple graph theory (which I do get Smiley).  

What I can't understand is how you build a graph that represents a map where the locations arn't grid based. Do you impose a grid onto the map to assist in building nodes and hence the graph?

Kev

Offline elias

Senior Member





« Reply #8 - Posted 2003-12-26 18:45:35 »

That's one possibility anyway - create a grid such that the smallest unit fits into a grid square. You can even make it coarser and still maintain the one-grid-to-one-unit mapping if you have larger variations in unit size. You just have to make sure that the unit go to the exact spot the player clicked on so the grid structure is not apparant to the him.

- elias

Online princec

JGO Kernel


Medals: 363
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #9 - Posted 2003-12-28 11:29:04 »

A* works with any topography. The nodes you create should represent the complete, discrete state at any one stage in the puzzle; and you must be able to provide a heuristic which guesses the cost of changing from one state to each of the possible adjacent states.

For a grid topology, the state can be very easily represented as a coordinate (x, y), and the adjacent states are likewise very easy to find, as they're the set of 8 coordinates surrounding (x, y). Likewise the cost is generally very easy to computed, based on some arbitrary "difficulty" of traversing the map at that point. Some states won't be possible because there's a wall in that map grid. The goal state is simply a node with the desired x,y coordinate. The SPGL AStarInt algorithm is optimised for simple tile maps and 2D grids.

It starts getting more interesting when you stop representing the world as a grid. A state in 3D would most likely consist of an approximate coordinate in space (given by x, y, z, r for example). The surrounding states would be perhaps generated by casting rays from that point in different directions. The goal state would be to be within a certain range of a goal coordinate gx, gy, gz.

The cost of getting from x1,y1,z1 to x2,y2,z2 would be dependent on your physics model. Going down is always easier than going up when there's gravity involved, so you might guess the cost of a route as being the distance in the 2D plane, plus a factor times the height if the height needs to be increased.

The SPGL algorithm is the basic A* algorithm. All the cleverness comes from your heuristics and choice of adjacent node states.

Cas Smiley

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Jeff

JGO Coder




Got any cats?


« Reply #10 - Posted 2003-12-28 17:23:29 »

Another simple dodge is to create a reasonably small grid such that grid squares are smaller then your objects.  Then consider any grid square an object intersects with to be "filled".  It means that in some cases you may end up with some "elbow room" but if the grid box size  == the maximal acceptable elbow room it aught to work.

OR jsut restrict object placement to the grid.  Thats how virtually every isometric game works today and they look and play fine Smiley

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Online kevglass

JGO Kernel


Medals: 158
Projects: 23
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Reply #11 - Posted 2003-12-30 10:06:39 »

Just wanted to pop back in and say thanks for the assistance, its working..

http://www.newdawnsoftware.com/martian/screenshots/301203_1.gif

Seems to pick some slightly odd routes now and again.

I'm currently using the "Manhattan" heuristic. Has anyone experimented with anything else and got good results?

Here's the reference I used should anyone want it in the future, its pretty good for a useless newbie like me:

http://www.policyalmanac.org/games/aStarTutorial.htm

Kev

Online kevglass

JGO Kernel


Medals: 158
Projects: 23
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Reply #12 - Posted 2003-12-30 11:14:40 »

I've actually put it in the game now and there are slight slow downs while the paths are found. Do I just need to keep trying to optimize the search routine or is threading likely to help?

Kev

Online kevglass

JGO Kernel


Medals: 158
Projects: 23
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Reply #13 - Posted 2003-12-30 14:01:32 »

I'm getting some pretty terrible times for searched relatively short paths with a good accuracy.

I guess I need to add waypoints in addition to the A* search paths?

Kev

Online princec

JGO Kernel


Medals: 363
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #14 - Posted 2003-12-30 20:18:51 »

The A* algorithm is very cunningly designed so it can be run one step at a time.

Rather than run it in a thread and risk it being run spuriously you need to timeslice it in your "thinking" thread, and run a specific number of steps at a time. While it's running the gidrahs don't move of course but that's all you can hope for. Or you can simply start them moving in the best direction yet found and correct it as the algorithm homes in on the best answer. Which is very like how people solve the same problem.

Cas Smiley

Offline webgeek

Junior Newbie




Java games rock!


« Reply #15 - Posted 2003-12-30 20:21:43 »

Waypoints can make all the difference. Using multiple pathfinding techniques will almost certainly get you both the most accurate and fastest possible path.

For instance, you can have way points that connect all "rooms" together and use something like Dijkstra's (sp) algorithm to search between them. Then you can use a 2d array to build a table of the fastest way between these points. This table would be generated when the level is generated and saved as part of it. I can explain this in more detail if you are interested. I have a sample Flash app I wrote that illustrates this too. I can dig it up if you want it (it was just a prototype, so don't expect much Wink).

To handle pathfinding within a room, you would still use A* but for cross-room pathfinding, you could use the way points. Using the two of these together can give you some fast and natural looking paths.

The problem then is handling collisions with other characters. A* is really good at a changing environment and way points are not unless you re-calculate paths between them when things change.

There are several articles about mixing algorithms in the Game Developer Gems books by Charles River (I own every one of those books and recomend them to everyone interested in this stuff). Don't miss the AI Game Wisdom book either. If you need the specific article, let me know and I can tell you the book and chapter title.

For some other interesting reading in those books, hit the articles by the BioWare guys about "depth of field/area of concern" stuff and the Ensable Studio guys about determining threats and LoS on a tile-based map.

Mike
mike@electrotank.com

[edit: fixed a typo + made last paragraph more clear ]
Online kevglass

JGO Kernel


Medals: 158
Projects: 23
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Reply #16 - Posted 2003-12-31 07:37:31 »

Well, thanks for the post! (you almost rival blahblahblah for scale of posts Wink). I've decided to not worry about it for a while, although I've added waypoints for the maps. Not really far enough long to be getting bogged down.

As to the entity/entity collision, I was considering allowing the entity to discover this on the fly and move "around" the blocking entity.

For my future reference, and others if they're reading this.. where might we find the BioWare articles?

Kev

EDIT: Incidently, I found DJK much easier to understand and implement than A*. Strange how minds work isn't it?

Offline webgeek

Junior Newbie




Java games rock!


« Reply #17 - Posted 2003-12-31 11:50:19 »

Yeah, I'll try to keep em shorter from now on Smiley

I edited the last post to make it more clear. The articles I was refering to in the last paragraph are in those Game Dev Gems books or AI Game Wisdom. I can find the specific details if you are so inclined. Thanks!

Mike
Online princec

JGO Kernel


Medals: 363
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #18 - Posted 2004-01-01 18:38:21 »

I think we should get Adam to post using MIME encoded zipped text to save on our bandwidth Wink

Cas Smiley

Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

CopyableCougar4 (22 views)
2014-08-22 19:31:30

atombrot (34 views)
2014-08-19 09:29:53

Tekkerue (30 views)
2014-08-16 06:45:27

Tekkerue (28 views)
2014-08-16 06:22:17

Tekkerue (18 views)
2014-08-16 06:20:21

Tekkerue (26 views)
2014-08-16 06:12:11

Rayexar (65 views)
2014-08-11 02:49:23

BurntPizza (41 views)
2014-08-09 21:09:32

BurntPizza (31 views)
2014-08-08 02:01:56

Norakomi (41 views)
2014-08-06 19:49:38
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!