Play Now Login Create Account
illyriad
  New Posts New Posts RSS Feed - Pathfinding - how hard is it?
  FAQ FAQ  Forum Search   Register Register  Login Login

Topic ClosedPathfinding - how hard is it?
 Post Reply Post Reply Page  <1234 5>
Author
 Rating: Topic Rating: 1 Votes, Average 5.00  Topic Search Topic Search  Topic Options Topic Options
abstractdream View Drop Down
Postmaster General
Postmaster General
Avatar

Joined: 02 Oct 2011
Location: Oarnamly
Status: Offline
Points: 1857 		Direct Link To This Post Posted: 26 Jan 2012 at 01:41
Certainly the implementation of pathfinding will be an elegant endeavor, if what Illyriad is now is any indication. This is a game that has never let me down and I'm sure it won't with this.
I really enjoy this thread, the speculation from players with more brains than I and the trickling of information from the GMs. I'm sure I speak for everyone in Elgea when I say:
"HURRY UP, ALREADY!"
Bonfyr Verboo
Back to Top
Albatross View Drop Down
Postmaster General
Postmaster General


Joined: 11 May 2011
Status: Offline
Points: 1118 		Direct Link To This Post Posted: 26 Jan 2012 at 00:16
:o) And after all this speculation about how hard it is, it will still be released in its own good time, using knowledge brought to the project from previous experience, fitting into that niche long-saved for it.

"and SC saw that it was good" - HonouredMule, August 2012.
Back to Top
Createure View Drop Down
Postmaster General
Postmaster General
Avatar

Joined: 07 Apr 2010
Location: uk
Status: Offline
Points: 1191 		Direct Link To This Post Posted: 25 Jan 2012 at 22:17
Originally posted by Nesse Nesse wrote:

No, you misunderstand me, Creature and Stormcrow!

What I am saying is NEVER MIND finding the closest, fastest or most direct route.


Ahh but this is Illy - we aren't happy with the crude approach!

We want cutting-edge approaches to the design from our devs and intricate gaming strategy and community interaction in our MMORTS so that ThunderCrow and StormCat can become buried under a heap of gold-plated game designers' awards and we can all become more deadly-efficient gaming veloci-raptors!

Personally I'm happy to wait that bit longer until we have something closer to this utopian ideal.


Edited by Createure - 25 Jan 2012 at 22:23
Back to Top
Nesse View Drop Down
Forum Warrior
Forum Warrior
Avatar

Joined: 03 Oct 2010
Location: England
Status: Offline
Points: 406 		Direct Link To This Post Posted: 25 Jan 2012 at 21:04
And yes, I get the pascal triangle bit too, but apart from not being the likely procedure for a caravan commander it is also too restrictive - you would like to travel in straight lines across same kind of terrain, turning at a well defined angle going from one terrain to another, rather than going stepwise square-by-square. There are obviously algorithms for that too, which I am sure Thundercat is infinitely (or at least n!) more familiar with than I am.
But what I'm trying to say is: don't overdo the "fastest" bit in fastest route! Also an extremely crude algorithm for finding a POSSIBLE route would be a good start and a welcome change from the flying caravans of today.
We, or at least I, would not expect my caravan drivers to do any better than stumbling along, and eventually getting there unless hijacked on the way. I might consider setting an ambush in a strategic position that wealthy caravans might pass, but interception I wouldn't even contemplate unless I had much faster units to send out to follow the enemy's footprints.


Edited by Nesse - 25 Jan 2012 at 21:05
Back to Top
Nesse View Drop Down
Forum Warrior
Forum Warrior
Avatar

Joined: 03 Oct 2010
Location: England
Status: Offline
Points: 406 		Direct Link To This Post Posted: 25 Jan 2012 at 20:25
No, you misunderstand me, Creature and Stormcrow!

What I am saying is NEVER MIND finding the closest, fastest or most direct route. That would not be the way it would be done in medieval times anyway. Instead, to go between ANY two points, not necessarily adjacent, choose one direction, until another direction is shorter. Or to make it even simpler, use only four directions. Then, going from (167,148) to (16,3) you would choose both
A) first the straight line from (167,148) to (167,3), then straight line (167,3) to (16,3)
or
B) first the straight line from (167,148) to (16,148), then straight line (16,148) to (16,3)
Then calculate which of those two is fastest (that's evaluating the terrain effects in 2*(151+145) squares, give or take four, but that should not take long, since the traveled route in all swuares except the end squares is exactly one square).

Oh, and then add the diagonals, making it marginally more difficult to find which two lines are "closest", and using traveled distance sqrt(2) per square for the diagonal.

But what would be fun would be using your own waypoints - maybe it would take research to establish the waypoint for caravans from that town?
Back to Top
Ander View Drop Down
Postmaster General
Postmaster General
Avatar

Joined: 24 Apr 2011
Status: Offline
Points: 1269 		Direct Link To This Post Posted: 25 Jan 2012 at 19:40
Originally posted by Createure Createure wrote:

everyone is right... just bracket confusion.

No, lisao is wrong! Tongue

Originally posted by lisao lisao wrote:


The solution should be (2n!) / (2n!)^2. The central part of pascals triangle.


It should be (2n!) / (n!)^2
Back to Top
Createure View Drop Down
Postmaster General
Postmaster General
Avatar

Joined: 07 Apr 2010
Location: uk
Status: Offline
Points: 1191 		Direct Link To This Post Posted: 25 Jan 2012 at 19:34
Quote Why assumed 2*? I meant (n!)*(n!).
Didn't really get to thinking about that part of it tbh - your mistake was (2n!) isn't (2n)!

Just bracket confusion going on.

TC seems very quietly confident about all this schabang. As I've just proved even relatively simple examples of pathfinding have the ability to confound people like me relatively rapidly when scaled up. Mucho respect.


Edited by Createure - 25 Jan 2012 at 19:42
Back to Top
lisao View Drop Down
New Poster
New Poster


Joined: 23 Jan 2012
Status: Offline
Points: 10 		Direct Link To This Post Posted: 25 Jan 2012 at 19:29

It is twelve years since I did any pathfinding, it is a very fascinating problem. Easy on a casual look, but very complex  if you have processor and/or memoryconstraints. 

The solution should be (2n!) / (2n!)^2. The central part of pascals triangle.



Edited by lisao - 25 Jan 2012 at 19:30
Back to Top
Ander View Drop Down
Postmaster General
Postmaster General
Avatar

Joined: 24 Apr 2011
Status: Offline
Points: 1269 		Direct Link To This Post Posted: 25 Jan 2012 at 19:29
Originally posted by Createure Createure wrote:

Originally posted by Ander Ander wrote:

(2n!)/((n!)(n!))

500 cows to google and 500 to wikipedia Tongue


Nice try, not quite though.

Assuming you meant (2n)! / 2*(n!) you get the sequence: 1 2 6 60 840

Why assumed 2*? Confused I meant (n!)*(n!). 
Since there is no option to write 'n! squared', I just chose to put it (n!)(n!)

I didnt mean to hijack the exciting thread. Too brainy for me. Please carry on you sparky folks!







Edited by Ander - 25 Jan 2012 at 19:33
Back to Top
Createure View Drop Down
Postmaster General
Postmaster General
Avatar

Joined: 07 Apr 2010
Location: uk
Status: Offline
Points: 1191 		Direct Link To This Post Posted: 25 Jan 2012 at 19:19
Originally posted by Ander Ander wrote:

(2n!)/((n!)(n!))

500 cows to google and 500 to wikipedia Tongue


Nice try, not quite though.

Assuming you meant (2n)! / 2*(n!) you get the sequence: 1 2 6 60 840

Or probably just a case of "wrongipedia" - answer is (2n)!/(n!)^2


Edited by Createure - 25 Jan 2012 at 19:32
Back to Top
 Post Reply Post Reply Page  <1234 5>
  Share Topic   

Forum Jump Forum Permissions View Drop Down

Forum Software by Web Wiz Forums® version 12.03
Copyright ©2001-2019 Web Wiz Ltd.