Game Development
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
User Name:
Password:
Remember me

The Shed is going Social! Join us on FaceBook and Twitter and chime in on the conversation.

Go Back   Dev Shed Forums > Programming Languages > Game Development
Reload this Page

SPF Algorythm?


Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
« Previous Thread | Next Thread »  
Thread Tools Search this Thread Rate Thread Display Modes
 
Unread Dev Shed Forums Sponsor:
  #1  
Old June 20th, 2006, 06:23 PM
adorablepuppy's Avatar
adorablepuppy adorablepuppy is offline
Come to the door. . .
Dev Shed Novice (500 - 999 posts)
  
Join Date: Mar 2004
Location: Ohio
Posts: 814 adorablepuppy User rank is First Lieutenant (10000 - 20000 Reputation Level)adorablepuppy User rank is First Lieutenant (10000 - 20000 Reputation Level)adorablepuppy User rank is First Lieutenant (10000 - 20000 Reputation Level)adorablepuppy User rank is First Lieutenant (10000 - 20000 Reputation Level)adorablepuppy User rank is First Lieutenant (10000 - 20000 Reputation Level)adorablepuppy User rank is First Lieutenant (10000 - 20000 Reputation Level)adorablepuppy User rank is First Lieutenant (10000 - 20000 Reputation Level)adorablepuppy User rank is First Lieutenant (10000 - 20000 Reputation Level) 
Time spent in forums: 2 Weeks 5 Days 16 h 44 m 24 sec
Reputation Power: 196
Send a message via MSN to adorablepuppy Send a message via Google Talk to adorablepuppy
SPF Algorythm?
Is there some sort of standard "shortest-path" algorythm strategy games use to move around obsticles?
__________________
The first dog icon I've EVER used!
Reply With Quote
  #2  
Old June 20th, 2006, 06:33 PM
M.Hirsch M.Hirsch is offline
Contributing User
Dev Shed God 1st Plane (5500 - 5999 posts)
  
Join Date: Oct 2000
Location: Back in the real world.
Posts: 5,966 M.Hirsch User rank is First Lieutenant (10000 - 20000 Reputation Level)M.Hirsch User rank is First Lieutenant (10000 - 20000 Reputation Level)M.Hirsch User rank is First Lieutenant (10000 - 20000 Reputation Level)M.Hirsch User rank is First Lieutenant (10000 - 20000 Reputation Level)M.Hirsch User rank is First Lieutenant (10000 - 20000 Reputation Level)M.Hirsch User rank is First Lieutenant (10000 - 20000 Reputation Level)M.Hirsch User rank is First Lieutenant (10000 - 20000 Reputation Level)M.Hirsch User rank is First Lieutenant (10000 - 20000 Reputation Level) 
Time spent in forums: 1 Month 2 Days 52 m 24 sec
Reputation Power: 189
Quote:
Originally Posted by adorablepuppy
Is there some sort of standard "shortest-path" algorythm strategy games use to move around obsticles?

Yes, it's called "A*".

There is a mathematical proof somewhere out there that says it produces the shortest path possible within a given time ... or so.... (sorry, no sources available right now)

Use it!

M.
__________________
--
Manuel Hirsch - Linux, FreeBSD, programming, administration articles, tutorials and more.
Reply With Quote
  #3  
Old June 20th, 2006, 07:28 PM
Viper_SB's Avatar
Viper_SB Viper_SB is offline
Psycho Canadian
Dev Shed Demi-God (4500 - 4999 posts)
  
Join Date: Jan 2001
Location: Canada
Posts: 4,845 Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level) 
Time spent in forums: 1 Month 1 Day 20 h 16 m 27 sec
Reputation Power: 634
Ya it doesn't always work though , at least in the older games and some newer ones.
Reply With Quote
  #4  
Old June 20th, 2006, 10:26 PM
pumpkin head pumpkin head is offline
what do I know about diamonds?
Dev Shed Novice (500 - 999 posts)
  
Join Date: Jul 2003
Location: ON, Canada
Posts: 950 pumpkin head User rank is First Lieutenant (10000 - 20000 Reputation Level)pumpkin head User rank is First Lieutenant (10000 - 20000 Reputation Level)pumpkin head User rank is First Lieutenant (10000 - 20000 Reputation Level)pumpkin head User rank is First Lieutenant (10000 - 20000 Reputation Level)pumpkin head User rank is First Lieutenant (10000 - 20000 Reputation Level)pumpkin head User rank is First Lieutenant (10000 - 20000 Reputation Level)pumpkin head User rank is First Lieutenant (10000 - 20000 Reputation Level)pumpkin head User rank is First Lieutenant (10000 - 20000 Reputation Level)  Folding Points: 51652 Folding Title: Beginner FolderFolding Points: 51652 Folding Title: Beginner FolderFolding Points: 51652 Folding Title: Beginner Folder
Time spent in forums: 1 Week 1 Day 35 m 53 sec
Reputation Power: 173
am i the only one confused?
__________________

Reply With Quote
  #5  
Old June 20th, 2006, 10:35 PM
para45's Avatar
para45 para45 is offline
﹌
Dev Shed Newbie (0 - 499 posts)
  
Join Date: Mar 2006
Posts: 264 para45 User rank is First Lieutenant (10000 - 20000 Reputation Level)para45 User rank is First Lieutenant (10000 - 20000 Reputation Level)para45 User rank is First Lieutenant (10000 - 20000 Reputation Level)para45 User rank is First Lieutenant (10000 - 20000 Reputation Level)para45 User rank is First Lieutenant (10000 - 20000 Reputation Level)para45 User rank is First Lieutenant (10000 - 20000 Reputation Level)para45 User rank is First Lieutenant (10000 - 20000 Reputation Level)para45 User rank is First Lieutenant (10000 - 20000 Reputation Level) 
Time spent in forums: 6 Days 2 h 28 m 19 sec
Reputation Power: 123
There are a few, but I've read only about Dijkstra's. Wikipedia has a list here http://en.wikipedia.org/wiki/Shortest_path.
Reply With Quote
  #6  
Old June 21st, 2006, 02:46 AM
displeaser's Avatar
displeaser displeaser is offline
Periodically energetic Perler
Dev Shed Regular (2000 - 2499 posts)
  
Join Date: May 2005
Location: Dublin, Ireland
Posts: 2,265 displeaser User rank is Colonel (50000 - 60000 Reputation Level)displeaser User rank is Colonel (50000 - 60000 Reputation Level)displeaser User rank is Colonel (50000 - 60000 Reputation Level)displeaser User rank is Colonel (50000 - 60000 Reputation Level)displeaser User rank is Colonel (50000 - 60000 Reputation Level)displeaser User rank is Colonel (50000 - 60000 Reputation Level)displeaser User rank is Colonel (50000 - 60000 Reputation Level)displeaser User rank is Colonel (50000 - 60000 Reputation Level)displeaser User rank is Colonel (50000 - 60000 Reputation Level)displeaser User rank is Colonel (50000 - 60000 Reputation Level)displeaser User rank is Colonel (50000 - 60000 Reputation Level)displeaser User rank is Colonel (50000 - 60000 Reputation Level)  Folding Points: 76661 Folding Title: Intermediate FolderFolding Points: 76661 Folding Title: Intermediate FolderFolding Points: 76661 Folding Title: Intermediate FolderFolding Points: 76661 Folding Title: Intermediate Folder
Time spent in forums: 4 Weeks 5 h 23 m 13 sec
Reputation Power: 536
Hi,

Heres the Perl AI::Pathfinding::Astar module up on CPAN, having a look at the perl source will explain the algo.
Heres a Link to an A* tutorial. And heres some general links to Game Pathfinding sites/info

Hope this helps.
Displeaser
__________________
Vi Veri Veniversum Vivus Vici.
Last edited by displeaser : June 21st, 2006 at 02:48 AM.
Reply With Quote
  #7  
Old June 21st, 2006, 08:19 AM
Viper_SB's Avatar
Viper_SB Viper_SB is offline
Psycho Canadian
Dev Shed Demi-God (4500 - 4999 posts)
  
Join Date: Jan 2001
Location: Canada
Posts: 4,845 Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level) 
Time spent in forums: 1 Month 1 Day 20 h 16 m 27 sec
Reputation Power: 634
Quote:
Originally Posted by displeaser
Hi,

Heres the Perl AI::Pathfinding::Astar module up on CPAN, having a look at the perl source will explain the algo.
Heres a Link to an A* tutorial. And heres some general links to Game Pathfinding sites/info

Hope this helps.
Displeaser
nice thanks
Reply With Quote
  #8  
Old June 21st, 2006, 08:41 AM
displeaser's Avatar
displeaser displeaser is offline
Periodically energetic Perler
Dev Shed Regular (2000 - 2499 posts)
  
Join Date: May 2005
Location: Dublin, Ireland
Posts: 2,265 displeaser User rank is Colonel (50000 - 60000 Reputation Level)displeaser User rank is Colonel (50000 - 60000 Reputation Level)displeaser User rank is Colonel (50000 - 60000 Reputation Level)displeaser User rank is Colonel (50000 - 60000 Reputation Level)displeaser User rank is Colonel (50000 - 60000 Reputation Level)displeaser User rank is Colonel (50000 - 60000 Reputation Level)displeaser User rank is Colonel (50000 - 60000 Reputation Level)displeaser User rank is Colonel (50000 - 60000 Reputation Level)displeaser User rank is Colonel (50000 - 60000 Reputation Level)displeaser User rank is Colonel (50000 - 60000 Reputation Level)displeaser User rank is Colonel (50000 - 60000 Reputation Level)displeaser User rank is Colonel (50000 - 60000 Reputation Level)  Folding Points: 76661 Folding Title: Intermediate FolderFolding Points: 76661 Folding Title: Intermediate FolderFolding Points: 76661 Folding Title: Intermediate FolderFolding Points: 76661 Folding Title: Intermediate Folder
Time spent in forums: 4 Weeks 5 h 23 m 13 sec
Reputation Power: 536
Reply With Quote
  #9  
Old June 21st, 2006, 10:19 AM
Viper_SB's Avatar
Viper_SB Viper_SB is offline
Psycho Canadian
Dev Shed Demi-God (4500 - 4999 posts)
  
Join Date: Jan 2001
Location: Canada
Posts: 4,845 Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level)Viper_SB User rank is Brigadier General (60000 - 70000 Reputation Level) 
Time spent in forums: 1 Month 1 Day 20 h 16 m 27 sec
Reputation Power: 634
Btw displeaser I added both your posts to the resources thread
Reply With Quote
  #10  
Old June 23rd, 2006, 12:46 PM
brett777 brett777 is offline
Registered User
Dev Shed Newbie (0 - 499 posts)
  
Join Date: Jun 2006
Posts: 8 brett777 User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 1 h 43 m 9 sec
Reputation Power: 0
If you can get hold of the Games Programming Gems series from Charles River (they are a bit pricey tho'), have a look at the index for Vol.4, there are 30 entries for Path Finding over the 4 volumes - doesn't cover vol. 5 which is out now.

If you like printed books - check out a good bookstore under Game Programming and Game AI - I think I remember seeing a series called something like Games AI or Games AI Gems last time I was in Waterstones that look pretty cool - and pretty expensive as well.
Reply With Quote
Reply

Viewing: Dev Shed Forums > Programming Languages > Game Development > SPF Algorythm?

« Previous Thread | Next Thread »

Developer Shed Advertisers and Affiliates



Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Linear Mode Linear Mode
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump

Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 


Powered by: vBulletin Version 3.0.5
Copyright ©2000 - 2013, Jelsoft Enterprises Ltd.

© 2003-2013 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap