Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

DarkBASIC Professional Discussion / Advanced pathfinding

Author
Message
mr Handy
18
Years of Service
User Offline
Joined: 7th Sep 2007
Location: out of TGC
Posted: 15th Jul 2012 16:11 Edited at: 15th Jul 2012 16:12
Link
Hi. I want to make pathfinding for units with different sizes, but I dont know how.

Here is the picture that demonstrates 3 types of units and generic collision map (for example A*).


Have you got any ideas how to implement such pathfinding?

«It's the Pony, pony me this, pony me that» — Bronies
«Socks are sexy. You should wear them!» — Bronies
«I sell apples and apple accessories» — Applejack
Back to top
Profile PM
basjak
16
Years of Service
User Offline
Joined: 16th Apr 2010
Location: feel like signing up for mars
Posted: 15th Jul 2012 16:28
Link
have you tried dark AI.

Back to top
Profile PM Email Website
mr Handy
18
Years of Service
User Offline
Joined: 7th Sep 2007
Location: out of TGC
Posted: 15th Jul 2012 17:31
Link
I need ideas not plugins

«It's the Pony, pony me this, pony me that» — Bronies
«Socks are sexy. You should wear them!» — Bronies
«I sell apples and apple accessories» — Applejack
Back to top
Profile PM
TheComet
18
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 15th Jul 2012 17:46 Edited at: 15th Jul 2012 17:48
Link
I'm actually also in search of a solution to this for PonyCraft! I'll keep an eye on this thread.

One idea that crossed my mind would be to have 3 layers for the pathfinder, one layer for every player that has a different size. You would store variations of the map into these arrays according to the size of the player.



When the function is called to search for the path you'd pass the size of the player to the function (type 1,2 or 3) and then use that to copy the layer into the pathfinder before searching for the path.



This method however would require a lot of pre-processing of the path data, making it harder to create maps.

TheComet


TimePlan : https://docs.google.com/spreadsheet/ccc?key=0AmuAKJolqASndEVYOWMxb3l2OWV0UkV1anRSczZScHc
Back to top
Profile PM Email Website
Pincho Paxton
23
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 15th Jul 2012 18:31
Link
You could make waypoints made from cubes that use sparky's to autoscale to fit themselves along a path. Then get the scale of each cube, and the scale of your figure. then make paths...

If figure < cube then path.

Back to top
Profile PM Email Website
mr Handy
18
Years of Service
User Offline
Joined: 7th Sep 2007
Location: out of TGC
Posted: 15th Jul 2012 21:28 Edited at: 15th Jul 2012 21:30
Link
@TheComet
The layers method had a problem - you can't calculate HALF-way:

* black lines are level 1 collision map
* red lines are level 2 collision map for big units
* green arrow is a way that big unit must walk

«It's the Pony, pony me this, pony me that» — Bronies
«Socks are sexy. You should wear them!» — Bronies
«I sell apples and apple accessories» — Applejack
Back to top
Profile PM
mr Handy
18
Years of Service
User Offline
Joined: 7th Sep 2007
Location: out of TGC
Posted: 16th Jul 2012 09:02
Link
@Pincho Paxton
No, that's not suitable, It will be perfomance killer even if will work.

«It's the Pony, pony me this, pony me that» — Bronies
«Socks are sexy. You should wear them!» — Bronies
«I sell apples and apple accessories» — Applejack
Back to top
Profile PM
Pincho Paxton
23
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 16th Jul 2012 10:44 Edited at: 16th Jul 2012 10:45
Link
Quote: "No, that's not suitable, It will be perfomance killer even if will work."


It would be an editor. You make the paths in the editor, save them as data. So fast during the game.

Back to top
Profile PM Email Website
mr Handy
18
Years of Service
User Offline
Joined: 7th Sep 2007
Location: out of TGC
Posted: 16th Jul 2012 11:28
Link
You mean path for every unit size? Then how's Warcraft 3 is made, there could be dozens of different size units on a custom map.

«It's the Pony, pony me this, pony me that» — Bronies
«Socks are sexy. You should wear them!» — Bronies
«I sell apples and apple accessories» — Applejack
Back to top
Profile PM
Pincho Paxton
23
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 16th Jul 2012 13:08 Edited at: 16th Jul 2012 13:12
Link
Quote: "You mean path for every unit size? Then how's Warcraft 3 is made, there could be dozens of different size units on a custom map."


Well units move individually usually, so that they squeeze through gaps by following a leader. It would be like the flight of birds routine that has rules to follow a leader, always keep a set distance apart etc. That would look more realistic. So in this case you only make a single path, and don't worry about the scale of it. Men who bump into a wall wait for a gap to follow the unit.

The picture you posted though was more like different sized people.

Back to top
Profile PM Email Website
TheComet
18
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 16th Jul 2012 14:28 Edited at: 16th Jul 2012 14:32
Link
@ Pincho

That's not helpful. Larger units could have entirely different paths. And for the record, the method you're trying to describe is called flocking.

Could you please only post about things you actually understand? I'm assuming you've never created or used a pathfinding algorithm before (you could try using one with 0 = 1 - 1, not sure how well that'd work out), so please keep hypotheses and other garbage like that to Geek Culture. This is a board where we need facts.

@ mrHandy

Are you using that advanced astar plugin, or do you have a custom function for your paths? I'm working on a small demo now with the layer solution and will be using that plugin which can be found here : IA::Astar

TheComet


TimePlan : https://docs.google.com/spreadsheet/ccc?key=0AmuAKJolqASndEVYOWMxb3l2OWV0UkV1anRSczZScHc
Back to top
Profile PM Email Website
Pincho Paxton
23
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 16th Jul 2012 15:12 Edited at: 16th Jul 2012 15:24
Link
Quote: "Could you please only post about things you actually understand? I'm assuming you've never created or used a pathfinding algorithm before (you could try using one with 0 = 1 - 1, not sure how well that'd work out), so please keep hypotheses and other garbage like that to Geek Culture. This is a board where we need facts."



There is nothing wrong with flocking in computer games, I have played Rollercoaster Tycoon 3 with flocking AI paths.

Quote: "
That's not helpful. Larger units could have entirely different paths. And for the record, the method you're trying to describe is called flocking."


Yes I included the different sized paths by using cube sizes.

Anyway I've reported you.

Back to top
Profile PM Email Website
TheComet
18
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 16th Jul 2012 15:42 Edited at: 16th Jul 2012 15:43
Link
Report me if you must. I'm just pointing out that this:

Quote: "You could make waypoints made from cubes that use sparky's to autoscale to fit themselves along a path. Then get the scale of each cube, and the scale of your figure. then make paths...

If figure < cube then path."


Isn't helpful because 1) it's inefficient, 2) "then make paths..." isn't as simple as that and 3) there's no way I can in any way picture what you said or convert what you said to any kind of code.

Quote: "There is nothing wrong with flocking in computer games, I have played Rollercoaster Tycoon 3 with flocking AI paths."


That doesn't answer what I said in any way.

Look, I'm sure you're a good guy and I'll admit, I'm very worried about you. Those locked threads and the things you've been saying lately are seriously making me concerned about you.

TheComet


TimePlan : https://docs.google.com/spreadsheet/ccc?key=0AmuAKJolqASndEVYOWMxb3l2OWV0UkV1anRSczZScHc
Back to top
Profile PM Email Website
mr Handy
18
Years of Service
User Offline
Joined: 7th Sep 2007
Location: out of TGC
Posted: 16th Jul 2012 15:52 Edited at: 16th Jul 2012 15:54
Link
@Pincho Paxton
Quote: "so that they squeeze through gaps by following a leader"

No no no, that's not it.

Quote: "Yes I included the different sized paths by using cube sizes."

You see,
Quote: "Warcraft 3 is made, there could be dozens of different size units on a custom map."

That means dozens of paths, for every size?
And... puff, some trees are cutted down. New path - recreate all paths on the fly?

@TheComet
Astar, yes. Is it latest - 1.0?

«It's the Pony, pony me this, pony me that» — Bronies
«Socks are sexy. You should wear them!» — Bronies
«I sell apples and apple accessories» — Applejack
Back to top
Profile PM
Pincho Paxton
23
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 16th Jul 2012 19:39 Edited at: 16th Jul 2012 19:39
Link
Quote: "That means dozens of paths, for every size?
And... puff, some trees are cutted down. New path - recreate all paths on the fly?"


Yes you can do that with cubes, you can get their scale, but never mind.

Back to top
Profile PM Email Website
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 16th Jul 2012 20:21
Link
I'm not sure what the original problem is.

If you have a pathfinding method that works for units of a certain size, why can't you just modify the logic of whatever test you are already using to rule out impossible moves?
Back to top
Profile PM Email
Diggsey
20
Years of Service
User Offline
Joined: 24th Apr 2006
Location: On this web page.
Posted: 16th Jul 2012 21:24 Edited at: 16th Jul 2012 21:46
Link
The solution to this problem is to modify the size of the obstacles rather than the size of the entity. Use the multiple layer method as TheComet suggested, but instead of having each layer a lower resolution, have them all the same resolution and increase the size of all the obstacles in each successive layer by one block width. Then you can just do normal pathfinding as long as you pick the correct layer.

An entity with a size of one block will pathfind using the lowest layer, an entity with a size of three blocks will pathfind using the next layer, etc. To get even entity sizes you must offset the grid by a half-square in each direction.



The white squares are the ones to be treated as walkable for each entity size from 1 to 4.

[b]
Back to top
Profile PM Email Website
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 17th Jul 2012 00:08
Link
Sounds like a good suggestion.
Back to top
Profile PM Email
Phaelax
DBPro Master
23
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 17th Jul 2012 02:17
Link
Quote: "Could you please only post about things you actually understand? I'm assuming you've never created or used a pathfinding algorithm before (you could try using one with 0 = 1 - 1, not sure how well that'd work out), so please keep hypotheses and other garbage like that to Geek Culture. This is a board where we need facts."


I'm with Pincho in that you're out of line. He's trying to help and you're basically calling him an idiot and his idea is nonsense.

Quite frankly, considering what little info was given by the OP, nobody ever stated whether or not the map data is static or dynamic. or anything else really other than, "hey I need pathfinding". We're not mind readers, we don't know what type of game he's making. So think before you go off on someone who's been on this forum twice as long as you and who's only trying to help.

"You're not going crazy. You're going sane in a crazy world!" ~Tick
Back to top
Profile PM Email Website
mr Handy
18
Years of Service
User Offline
Joined: 7th Sep 2007
Location: out of TGC
Posted: 17th Jul 2012 09:15 Edited at: 17th Jul 2012 09:20
Link
@Diggsey
Good idea!

Also, on layer 2 you have vertical path (down-left corner) for 2-block unit. But path in not in the middle of ther road, so basically unit will partially inserts into left wall. No?
I think initial resolution must be higher, so we can calculate half-ways between actual blocks.


Also, if the map is dynamic? Like trees or buildings in rts?

«It's the Pony, pony me this, pony me that» — Bronies
«Socks are sexy. You should wear them!» — Bronies
«I sell apples and apple accessories» — Applejack
Back to top
Profile PM
TheComet
18
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 17th Jul 2012 11:17
Link
Quote: "Quite frankly, considering what little info was given by the OP, nobody ever stated whether or not the map data is static or dynamic. or anything else really other than, "hey I need pathfinding". We're not mind readers, we don't know what type of game he's making. So think before you go off on someone who's been on this forum twice as long as you and who's only trying to help."


I apologise for my behavior, I agree I was out of line and will accept any punishments that may be held against me.

TheComet


TimePlan : https://docs.google.com/spreadsheet/ccc?key=0AmuAKJolqASndEVYOWMxb3l2OWV0UkV1anRSczZScHc
Back to top
Profile PM Email Website
TheComet
18
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 17th Jul 2012 12:06
Link
@ mrHandy

Not my most efficient coding, I tried expanding it so it would be easy to understand. You should add another dimension to every array so you don't have to type things 3 times.



Next thing to do would be to come up with an algorithm that can procedurally generate the other layers based on the first layer. I already have an idea and will see if it works or not. You'll hear from me again either way.

TheComet


TimePlan : https://docs.google.com/spreadsheet/ccc?key=0AmuAKJolqASndEVYOWMxb3l2OWV0UkV1anRSczZScHc
Back to top
Profile PM Email Website
Diggsey
20
Years of Service
User Offline
Joined: 24th Apr 2006
Location: On this web page.
Posted: 17th Jul 2012 15:09
Link
Quote: "Also, on layer 2 you have vertical path (down-left corner) for 2-block unit. But path in not in the middle of ther road, so basically unit will partially inserts into left wall. No?
I think initial resolution must be higher, so we can calculate half-ways between actual blocks."


That's why I said to add the half-block offset. If you look at the diagram you can see the red square over the layer for size 2 entities. This is where the normal layers would be in relation to it. With this adjustment for all the even layers there is no need to go to a higher resolution.

Quote: "Also, if the map is dynamic? Like trees or buildings in rts?"


Just modify the base layer and then recalculate the higher layers from that. It is a very simple calculation:

To go from an odd layer to the next even layer (eg. 1 -> 2), for each solid block, make the blocks above, left and above-left solid as well if they are not already.

To go from an even layer to the next odd layer (eg. 2 -> 3), for each solid block make the blocks below, right and below-right solid as well if they are not already.

You can make this more efficient by only updating the region that you modify.

[b]
Back to top
Profile PM Email Website
mr Handy
18
Years of Service
User Offline
Joined: 7th Sep 2007
Location: out of TGC
Posted: 17th Jul 2012 15:35
Link
@Diggsey
Well, I should try that half-block offset thing. Thanks!

@TheComet
a2fillbox - what is it?

«Socks are sexy. You should wear them!» — Bronies
Back to top
Profile PM
TheComet
18
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 17th Jul 2012 16:00
Link
A sorry, it's from the Advanced2D plugin : http://forum.thegamecreators.com/?m=forum_view&t=179096&b=5

It's a set of much faster 2D commands. You can replace it with the native box command though. And you also might need this:



Sorry for all of that, I sometimes get confused with what are plugins and what are native commands.

TheComet


TimePlan : https://docs.google.com/spreadsheet/ccc?key=0AmuAKJolqASndEVYOWMxb3l2OWV0UkV1anRSczZScHc
Back to top
Profile PM Email Website
mr Handy
18
Years of Service
User Offline
Joined: 7th Sep 2007
Location: out of TGC
Posted: 17th Jul 2012 17:35
Link
Interesting plugin I'll take a closer look later.
offtopic: do you know any plugin that can copy image from [set camera to image] to new/existing image?

«Socks are sexy. You should wear them!» — Bronies
Back to top
Profile PM
TheComet
18
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 17th Jul 2012 17:47
Link
Image Kit does that with the command IK paste image on image.

http://forum.thegamecreators.com/?m=forum_view&t=177340&b=5

TheComet


TimePlan : https://docs.google.com/spreadsheet/ccc?key=0AmuAKJolqASndEVYOWMxb3l2OWV0UkV1anRSczZScHc
Back to top
Profile PM Email Website
mr Handy
18
Years of Service
User Offline
Joined: 7th Sep 2007
Location: out of TGC
Posted: 18th Jul 2012 09:07 Edited at: 18th Jul 2012 09:08
Link
@TheComet Cool!

I think layer pathfinding is good, just add dynamic updates and quick layer compilation. What about Warcraft3 - I think their units size is approximate, it means units with alike % size are using one layer.

«Socks are sexy. You should wear them!» — Bronies
Back to top
Profile PM
noobnerd
15
Years of Service
User Offline
Joined: 30th Nov 2010
Location:
Posted: 18th Jul 2012 20:14
Link
im no expert on this but i ave done some programs that use A*.

i would suggest calculating an "area" for each node and storing them in an array. just check how many white boxes are adjacent to a node and give it an area according to that number, and if its got the maximum of 8 adjacent ones you could then check one step outward and so on. this way coorners would kinda be smoothed out though. just a thought.

a one box wide path would have each node an area of 2 so that is the lowest value kinda. with some tinkering (such as allowing it to expand even if only 7 adjacent ones were open) would allow large things like tanks and such "ignore" or "destroy" small stuff like rocks/trees/corners on its way. a living thin like a troll is after all somewhat flexible and should be able to squeeze past slightly narrow places ( such as the diagonal gap between 2 houses that are placed diagonally away from eac other).
Back to top
Profile PM
Back to top

Login to post a reply

Server time is: 2026-07-07 14:22:34
Your offset time is: 2026-07-07 14:22:34