Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (541)
Games in Android Showcase (133)
games submitted by our members
Games in WIP (603)
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  
  A* with different sized units  (Read 4023 times)
0 Members and 1 Guest are viewing this topic.
Offline counterp

Senior Devvie


Medals: 11



« Posted 2012-07-06 07:12:33 »

http://aigamedev.com/open/tutorial/clearance-based-pathfinding/

Is there a java implementation of this, or any pathfinding that allows for different sized units instead of 1 per tile? A unit that takes up 4 tiles (2x2)? And the unit is not necessarily a square unit, they maybe rectangular for example taking up 2 tiles (1x2).

I've got A* down, but I need to figure this out (more explanations also help)
Offline ReBirth
« Reply #1 - Posted 2012-07-06 13:59:15 »

How about treat that 2x2 tile as 4 1x1 tiles? and so for the rest sizes.

Offline UprightPath
« Reply #2 - Posted 2012-07-06 17:18:22 »

M-m-m-m-multiple maps!!! It would take some pre-processing of each map, however you can build several versions on the same map, each one tailored to a specific 'size' of unit.

Then, when a creature moves, it searches the map constructed for its size. If you're worried about a dynamic map (creatures cannot overlap/move through each other at any point) then you just make sure that each logical tile in your game knows which map tiles it belongs to. When an entity moves over one, you update each map tile to say that it's overlapped.

Depending on your target platform, the size of the maps, etc, this might be over kill in some way, but iit's possible that it's faster than trying the 2x2 or 3x2 or whatever each time.

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

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #3 - Posted 2012-07-06 18:07:52 »

M-m-m-m-multiple maps!!! It would take some pre-processing of each map, however you can build several versions on the same map, each one tailored to a specific 'size' of unit.

Did you read the link? The whole point of clearance based pathfinding is to only store one clearance map that can be used with A* to calculate a path for a suitably big/small object.

counterp: was there anything specific you were having problems with? The clearance based A* seems relatively straightforward (the hierarchical stuff... less so. Smiley )

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline UprightPath
« Reply #4 - Posted 2012-07-07 06:13:05 »

Derp. I fail. I blame the fact that I'm currently trying to reply to things/read from my Android phone. >.> I should probably actually read/notice links.

Offline counterp

Senior Devvie


Medals: 11



« Reply #5 - Posted 2012-07-07 07:05:33 »

I didn't quite understand how to set a clearance value for each tile for starters, (1, 2, 3, 4, 5, etc) so I thought looking at a java implementation would help

@ReBirth not sure what you meant
Offline ReBirth
« Reply #6 - Posted 2012-07-07 10:46:49 »

I didn't quite understand how to set a clearance value for each tile for starters, (1, 2, 3, 4, 5, etc) so I thought looking at a java implementation would help

@ReBirth not sure what you meant
Treat a big tile as some small 1x1 tiles.

Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #7 - Posted 2012-07-07 10:50:58 »

It's explained at the "The True Clearance Metric" bit. Basically for each tile you find out how far right and down you can extend it without hitting an impassable tile. That width/height is the clearance value.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline counterp

Senior Devvie


Medals: 11



« Reply #8 - Posted 2012-07-07 13:14:47 »

problem is I have an 'infinite' map, is the only way to keep recalculating each time a new area has been discovered?

I didn't quite understand how to set a clearance value for each tile for starters, (1, 2, 3, 4, 5, etc) so I thought looking at a java implementation would help

@ReBirth not sure what you meant
Treat a big tile as some small 1x1 tiles.

You mean a 2x2 tile as 4 seperate 1x1 tiles? but how would that even work
Offline UprightPath
« Reply #9 - Posted 2012-07-07 21:50:27 »

Fy, rom what's been said, I think I understand the problem (Yay!), but I still haven't actually read the page yet (I'm just responding/talking through my little phone while I try to make a section of my house wheel chair accessible.)

Anyway, it seems that for an arbitary sized/shaped map (let's call it that, instead of infinite) that you have a few options.

1) Recompute the clearrance when more areas becoming visible.

2) Compute the clearance as soon as you can. However, this let's the path finder sort of "see beyond" the sight area of the creature when picking a route (the pathfinder gets the clearance values, which indicates open spaces, meaning it'll know where the creature can fit before it gets close enough to see.)

3) Attempt to disable the clearance path finding through unseen areas. Not sure how to accurately do this though.

4) Make a maximum limit on the clearance value of each tile (the smallest you can, and still fit your largest creature). Then, instead of recomputing each time you discover an area, you just mark a 'seen' flag, if it's seen, then you get it's actual clearnce values, if it's unseen you get it's unseen values (preferably either the maximum-- so that your path finder will assume that any sized creature can move through an unseen path-- or some arbitrary other value.) Still has the issue that the path finder can see a bit beyond the edges of the creature's vision (tiles on the edge of vision in certain directions with give information about what's further in that direction).


If you give us some idea about what you're trying to do: how you're genetrating your map, whwther vision matters (sort of assuming from what you said), etc. We might be able to give you an answer to better suit your needs.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Gudradain
« Reply #10 - Posted 2012-07-07 23:33:31 »

Woah, clearance map are so simple and easy, I absolutely love it Smiley

My first idea would have been to regroup 4 1x1 tile together and do some fancy iterating through it but the clearance map idea is so much more elegant and probably faster.

If I was you I would stick to square unit. It will make your life easier. Even if the unit is square you can make it look like if it is rectangular. Most RTS do it this way; some unit have recrangle graphic but when you test their collision detection it's obviously square.
Offline UprightPath
« Reply #11 - Posted 2012-07-08 01:08:35 »

Woah, clearance map are so simple and easy, I absolutely love it Smiley

My first idea would have been to regroup 4 1x1 tile together and do some fancy iterating through it but the clearance map idea is so much more elegant and probably faster.

If I was you I would stick to square unit. It will make your life easier. Even if the unit is square you can make it look like if it is rectangular. Most RTS do it this way; some unit have recrangle graphic but when you test their collision detection it's obviously square.

It should relatively simple to make rectangular units work. Keep X & Y clearance seperate, then have an internal variablein a unit that states whether it's rotated/oriented along some axis. Your path finder would have to know whether how to change the orientation to fit, but all in all that should only increase the number of possible nodes by a rather minor number. (Whether turning would count as an action/costly operation when the path finder searches is up to you.)

Offline counterp

Senior Devvie


Medals: 11



« Reply #12 - Posted 2012-07-08 10:31:53 »

Fy, rom what's been said, I think I understand the problem (Yay!), but I still haven't actually read the page yet (I'm just responding/talking through my little phone while I try to make a section of my house wheel chair accessible.)

Anyway, it seems that for an arbitary sized/shaped map (let's call it that, instead of infinite) that you have a few options.

1) Recompute the clearrance when more areas becoming visible.

2) Compute the clearance as soon as you can. However, this let's the path finder sort of "see beyond" the sight area of the creature when picking a route (the pathfinder gets the clearance values, which indicates open spaces, meaning it'll know where the creature can fit before it gets close enough to see.)

3) Attempt to disable the clearance path finding through unseen areas. Not sure how to accurately do this though.

4) Make a maximum limit on the clearance value of each tile (the smallest you can, and still fit your largest creature). Then, instead of recomputing each time you discover an area, you just mark a 'seen' flag, if it's seen, then you get it's actual clearnce values, if it's unseen you get it's unseen values (preferably either the maximum-- so that your path finder will assume that any sized creature can move through an unseen path-- or some arbitrary other value.) Still has the issue that the path finder can see a bit beyond the edges of the creature's vision (tiles on the edge of vision in certain directions with give information about what's further in that direction).


If you give us some idea about what you're trying to do: how you're genetrating your map, whwther vision matters (sort of assuming from what you said), etc. We might be able to give you an answer to better suit your needs.

Yes I just thought of #4 yesterday and all is going well. I'm just gonna finish making it work with rectangular units and all should be well.

Thanks for pointing me in the right direction guys
Offline counterp

Senior Devvie


Medals: 11



« Reply #13 - Posted 2012-07-08 11:41:48 »

Well here is a graphical demo - completely unoptimized (didn't even merge clearances with node class, and new nodes are generated each time a path is found instead of saving them), possibly not even working properly, I don't feel like thinking for a while.

http://www.java-gaming.org/?action=pastebin&id=143

By default the unit size is 2x3

Thanks again, feel free to point out any flaws, and you may tell me any suggestions for optimization (I already have a couple of ideas)
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.

Mr.CodeIt (10 views)
2014-12-27 04:03:04

TheDudeFromCI (13 views)
2014-12-27 02:14:49

Mr.CodeIt (25 views)
2014-12-23 03:34:11

rwatson462 (56 views)
2014-12-15 09:26:44

Mr.CodeIt (46 views)
2014-12-14 19:50:38

BurntPizza (92 views)
2014-12-09 22:41:13

BurntPizza (113 views)
2014-12-08 04:46:31

JscottyBieshaar (83 views)
2014-12-05 12:39:02

SHC (94 views)
2014-12-03 16:27:13

CopyableCougar4 (102 views)
2014-11-29 21:32:03
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

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
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!