Jump to content

  • Log In with Google      Sign In   
  • Create Account

A* turning and unit direction


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
7 replies to this topic

#1 PantherBoy   Members   -  Reputation: 163

Like
0Likes
Like

Posted 17 July 2012 - 09:38 PM

Hello all,

I'm currently spending some time trying to improve my pathfinding library and was looking for some ideas on how to deal with direction of units and their turn radius.

For example if a unit had its back to the target, a straight line path wouldn't be suitable as returned by A* (assuming no clear path between unit and target) as the unit would have to rotate around, and the turn radius could potentially make it follow a path that touches grid cells that where not in the original calculated clear path and over cells has a blocking obstacle.

My original thinking was to factor the direction cost into the heuristic function of the A* algorithm but its getting pretty messy and not very reliable so I thought id ask if others have implemented anything similar, thinks this is the wrong approach and has better ideas or even can point me to any helpful papers/articles.


Thanks!

Sponsor:

#2 PantherBoy   Members   -  Reputation: 163

Like
0Likes
Like

Posted 17 July 2012 - 09:43 PM

Sorry I'm not sure how but I double posted by accident, the other double post has now been deleted

Edited by PantherBoy, 20 July 2012 - 04:05 PM.


#3 snowmanZOMG   Members   -  Reputation: 909

Like
2Likes
Like

Posted 21 July 2012 - 10:01 PM

I have also been investigating various pathfinding solutions that take into account a turn radius and agent orientation. The most useful article I've seen so far on this matter is http://www.gamasutra...pathfinding.php where they essentially make the orientation information a part of their search state space and rule out certain tiles based on the given turning radius during the search.

It's a rather old article, but I think lots of the information there is still relevant. There's also a presentation floating around on aigamedev about some pathing goodness from Company of Heroes, but if I recall, that presentation is a little light on details with regard to their vehicular movement.

#4 IADaveMark   Moderators   -  Reputation: 2531

Like
1Likes
Like

Posted 22 July 2012 - 11:46 PM

The CoH one was done by Chris Jurney. There's a good article on it in AI Game Programming Wisdom 4.
Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

#5 PantherBoy   Members   -  Reputation: 163

Like
0Likes
Like

Posted 24 July 2012 - 07:32 PM

Thanks snowmanZOMG and IADaveMark, that Chris Jurney article seems very interesting and looks like it discusses exactly what I was after. The bad news is the book is out of print and used copies seem to be retailing upwards of $400 on amazonPosted Image . The demand for that book must be very high, wish there was an ebook version I could buy.

I'm going to have to try and find someone who has it and can lend it me Posted Image

#6 GlenDC   Members   -  Reputation: 545

Like
0Likes
Like

Posted 25 July 2012 - 05:07 AM

You can still find the book on the world wide web. If you don't wanna pay because your a poor student or don't have the money for it for other reasons than you can always download it. This is not wrong in my opinion to do, it's just like sharing books, like they do with small books in the metro stations Posted Image

Oh, and thank you snowmanZOMG for your shared information!

Edit: Damnit can't find a correct version of the ebook version. Does anyone have a working ebook version of it available online ?

Edited by GlenDC, 25 July 2012 - 07:05 AM.


#7 IADaveMark   Moderators   -  Reputation: 2531

Like
1Likes
Like

Posted 25 July 2012 - 08:45 AM

The publisher said they are working on a Kindle version at the moment. Trust me, hilarity ensued when the bots bid the price up to $400. Posted Image
Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

#8 GlenDC   Members   -  Reputation: 545

Like
0Likes
Like

Posted 25 July 2012 - 09:16 AM

Awesome, than I can read it on my lovely Kindle. Thanks IADaveMark for the information. It's pretty insane that the price is so high oO




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS