Game Development
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
User Name:
Password:
Remember me
Go Back   Dev Shed Forums > Programming Languages > Game Development
Reload this Page

SPF Algorythm?

Discuss SPF Algorythm? in the Game Development forum on Dev Shed.
SPF Algorythm? Game Development forum covering non language specific programming - game creation, design, modding, theories and math. A place for developers and gamers of all levels to discuss and debate all things involved in game creation and modding.

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:
Stop making mediocre tutorials.The best tutorials are video! Camtasia Studio makes it easy to create engaging, buzz-building screen videos at any size, in any popular format. Download the free trial!
  #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: 812 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 11 h 7 m 23 sec
Reputation Power: 142
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,969 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 1 Day 22 h 39 m 55 sec
Reputation Power: 184
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,739 Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level) 
Time spent in forums: 4 Weeks 6 h 25 m 16 sec
Reputation Power: 384
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 23 m 45 sec
Reputation Power: 168
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: 261 para45 User rank is Sergeant Major (2000 - 5000 Reputation Level)para45 User rank is Sergeant Major (2000 - 5000 Reputation Level)para45 User rank is Sergeant Major (2000 - 5000 Reputation Level)para45 User rank is Sergeant Major (2000 - 5000 Reputation Level)para45 User rank is Sergeant Major (2000 - 5000 Reputation Level)para45 User rank is Sergeant Major (2000 - 5000 Reputation Level) 
Time spent in forums: 6 Days 1 h 23 m 59 sec
Reputation Power: 43
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,266 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: 531
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,739 Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level) 
Time spent in forums: 4 Weeks 6 h 25 m 16 sec
Reputation Power: 384
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,266 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: 531
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,739 Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level)Viper_SB User rank is Major (30000 - 40000 Reputation Level) 
Time spent in forums: 4 Weeks 6 h 25 m 16 sec
Reputation Power: 384
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 »

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

 Free IT White Papers!
 
Accelerating Trading Partner Performance
One in five. That's how many partner transactions have at least one error. That is an amazing statistic, particularly given the extraordinary leaps in innovation across the global supply chain during the past two decades. Download this white paper to learn more.
 
Competing on Analytics
This Tech Analysis is designed to help identify characteristics shared by analytics competitors, and includes information about 32 organizations that have made a commitment to quantitative, fact-based analysis.
 
Cost Effective Scaling with Virtualization and Coyote Point Systems
An overview of the industry trend toward virtualization, how server consolidation has increased the importance of application uptime and the steps being taken to integrate load balancing technology with virtualized servers.
 
Five Checkpoints to Implementing IP Telephony
Implementation planning for IP PBX software and IP telephony has become vital as businesses replace discontinued legacy PBX phone systems. This informative whitepaper outlines five "checkpoints" for any implementation plan that will help make IP communications a successful proposition.
 
Hosted Email Security: Staying Ahead of New Threats
In the last two years, email has become a fierce battleground between the nefarious forces of spam and malware, and the heroes of messaging protection. The spam volumes increased alarmingly every month, bringing clever new forms of phishing and virus propagation attacks.
 

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