IPB

Welcome Guest ( Log In | Register )

 
Reply to this topicStart new topic
> Pathfinder
Mordion
post Sep 22 2018, 01:33 AM
Post #1


Vagabond
**

Group: Members Plus
Posts: 101
Joined: 30-September 07
Member No.: 3,924
referrer:The Super Seer



I just wrote a program that will find the shortest path from A to B in the dungeon. Are there any routes you'd like to see? Here's the fastest route to 15

CODE

9,11,1
9,12,1
8,12,1
7,12,1
7,11,1
7,10,1
7,9,1
7,8,1
8,8,1
9,8,1
10,8,1
10,7,1
10,6,1
9,6,1
8,6,1
7,6,1
7,6,2
7,7,2
8,7,2
8,6,2
9,6,2
10,6,2
10,7,2
10,8,2
10,9,2
10,10,2
9,10,2
9,11,2
9,12,2
9,13,2
10,13,2
11,13,2
11,14,2
12,14,2
13,14,2
13,15,2
14,15,2
15,15,2
16,15,2
16,14,2
17,14,2
17,13,2
17,13,3
17,14,3
17,15,3
17,16,3
18,16,3
19,16,3
20,16,3
20,17,3
20,18,3
20,19,3
21,19,3
22,19,3
22,20,3
21,20,3
21,20,4
20,20,4
20,20,5
21,20,5
21,20,6
21,21,6
21,22,6
21,23,6
21,24,6
21,25,6
21,26,6
20,26,6
19,26,6
18,26,6
17,26,6
16,26,6
16,27,6
16,28,6
16,29,6
15,29,6
14,29,6
14,28,6
13,28,6
12,28,6
11,28,6
11,29,6
11,29,7
11,30,7
10,30,7
10,30,10
11,30,10
11,29,10
12,29,10
13,29,10
13,30,10
14,30,10
15,30,10
15,29,10
16,29,10
17,29,10
17,30,10
18,30,10
19,30,10
20,30,10
20,30,13
20,29,13
21,29,13
22,29,13
23,29,13
23,28,13
24,28,13
24,27,13
24,26,13
24,25,13
24,24,13
24,23,13
24,22,13
23,22,13
23,21,13
23,20,13
23,19,13
23,18,13
23,17,13
23,16,13
22,16,13
21,16,13
21,15,13
21,14,13
20,14,13
20,13,13
20,12,13
21,12,13
22,12,13
22,13,13
22,14,13
23,14,13
23,13,13
23,13,14
24,13,14
24,12,14
24,11,14
24,10,14
23,10,14
22,10,14
21,10,14
20,10,14
19,10,14
18,10,14
17,10,14
16,10,14
15,10,14
14,10,14
14,9,14
14,8,14
14,7,14
15,7,14
16,7,14
17,7,14
17,6,14
17,5,14
17,4,14
17,3,14
16,3,14
15,3,14
15,2,14
14,2,14
13,2,14
13,3,14
13,4,14
13,4,15


and back

CODE

13,4,15
13,3,15
13,3,14
13,2,14
14,2,14
15,2,14
15,3,14
16,3,14
17,3,14
17,4,14
17,5,14
17,6,14
17,7,14
16,7,14
15,7,14
14,7,14
14,8,14
14,9,14
14,10,14
15,10,14
16,10,14
17,10,14
18,10,14
19,10,14
20,10,14
20,11,14
20,12,14
21,12,14
22,12,14
23,12,14
24,12,14
24,13,14
23,13,14
23,13,13
23,14,13
22,14,13
22,13,13
22,12,13
21,12,13
20,12,13
20,13,13
20,14,13
19,14,13
19,13,13
19,12,13
18,12,13
17,12,13
16,12,13
15,12,13
14,12,13
14,11,13
13,11,13
12,11,13
12,10,13
11,10,13
10,10,13
10,9,13
9,9,13
8,9,13
7,9,13
6,9,13
5,9,13
4,9,13
4,8,13
4,7,13
3,7,13
2,7,13
2,6,13
1,6,13
1,6,12
1,7,12
1,8,12
1,9,12
1,10,12
1,11,12
1,12,12
1,13,12
2,13,12
2,14,12
2,15,12
2,16,12
1,16,12
1,17,12
1,18,12
1,19,12
2,19,12
3,19,12
4,19,12
4,20,12
4,21,12
5,21,12
6,21,12
7,21,12
7,20,12
7,19,12
8,19,12
8,19,11
8,20,11
8,21,11
9,21,11
10,21,11
11,21,11
11,22,11
11,22,10
11,21,10
11,20,10
11,19,10
11,18,10
11,17,10
11,16,10
11,15,10
11,14,10
11,13,10
11,12,10
12,12,10
13,12,10
13,11,10
12,11,10
11,11,10
10,11,10
10,12,10
9,12,10
8,12,10
8,11,10
7,11,10
6,11,10
5,11,10
4,11,10
4,12,10
4,13,10
3,13,10
3,14,10
3,15,10
4,15,10
4,16,10
4,17,10
3,17,10
2,17,10
1,17,10
1,18,10
2,18,10
3,18,10
3,18,9
3,17,9
3,16,9
3,15,9
4,15,9
4,14,9
4,13,9
4,12,9
3,12,9
2,12,9
2,13,9
2,14,9
2,15,9
2,16,9
1,16,9
1,17,9
1,18,9
2,18,9
2,19,9
2,20,9
3,20,9
3,21,9
3,22,9
3,23,9
3,24,9
4,24,9
4,25,9
4,26,9
3,26,9
3,27,9
4,27,9
3,2,8
3,3,8
2,3,8
2,4,8
2,5,8
2,6,8
2,7,8
2,8,8
2,9,8
2,10,8
2,11,8
1,11,8
1,12,8
1,13,8
1,14,8
2,14,8
3,14,8
3,15,8
2,15,8
1,15,8
1,16,8
1,17,8
1,18,8
1,19,8
1,20,8
2,20,8
2,20,7
2,21,7
3,21,7
3,22,7
3,23,7
3,24,7
3,25,7
3,26,7
4,26,7
5,26,7
5,27,7
5,28,7
6,28,7
7,28,7
8,28,7
8,27,7
8,26,7
8,25,7
9,25,7
10,25,7
11,25,7
12,25,7
13,25,7
14,25,7
15,25,7
16,25,7
17,25,7
17,26,7
16,26,7
15,26,7
15,27,7
15,28,7
14,28,7
13,28,7
13,27,7
12,27,7
12,28,7
12,29,7
11,29,7
11,29,6
11,28,6
12,28,6
13,28,6
13,29,6
14,29,6
15,29,6
16,29,6
16,28,6
16,27,6
16,26,6
16,25,6
16,24,6
16,23,6
17,23,6
18,23,6
19,23,6
20,23,6
21,23,6
21,22,6
21,21,6
21,20,6
21,20,5
22,20,5
23,20,5
23,20,4
24,20,4
25,20,4
25,21,4
25,22,4
25,23,4
24,23,4
23,23,4
23,24,4
22,24,4
22,25,4
21,25,4
21,24,4
21,23,4
21,22,4
21,21,4
21,20,4
21,20,3
22,20,3
22,19,3
22,18,3
21,18,3
20,18,3
20,17,3
20,16,3
19,16,3
18,16,3
17,16,3
17,15,3
17,14,3
17,13,3
17,12,3
18,12,3
18,11,3
18,10,3
17,10,3
16,10,3
15,10,3
14,10,3
13,10,3
12,10,3
12,11,3
12,12,3
12,13,3
12,13,2
11,13,2
10,13,2
9,13,2
9,12,2
9,11,2
9,10,2
10,10,2
10,9,2
10,8,2
10,7,2
10,6,2
9,6,2
9,7,2
8,7,2
7,7,2
7,6,2
7,6,1
8,6,1
9,6,1
10,6,1
10,7,1
10,8,1
9,8,1
8,8,1
7,8,1
7,9,1
7,10,1
7,11,1
7,12,1
8,12,1
9,12,1
9,11,1


Go to the top of the page
 
+Quote Post
Mordion
post Sep 22 2018, 05:57 PM
Post #2


Vagabond
**

Group: Members Plus
Posts: 101
Joined: 30-September 07
Member No.: 3,924
referrer:The Super Seer



I tweaked it to give it one use of Ethereal portal and it shaved off 15 steps. All of these paths surprise me. I guess I'm just old fashioned for taking the stairs.

CODE
9,11,1
9,12,1
8,12,1
7,12,1
7,11,1
7,10,1
7,9,1
7,8,1
8,8,1
9,8,1
10,8,1
10,7,1
10,6,1
9,6,1
8,6,1
7,6,1
7,6,2
7,5,2
6,5,2
5,5,2
5,6,2
5,7,2
4,7,2
3,7,2
3,8,2
3,8,3
2,8,3
2,9,3
3,9,3
3,10,3
3,11,3
3,12,3
3,13,3
3,14,3
3,15,3
3,16,3
2,16,3
1,16,3
1,17,3
22,20,3
21,20,3
21,20,4
20,20,4
20,20,5
21,20,5
21,20,6
21,21,6
21,22,6
21,23,6
20,23,6
19,23,6
18,23,6
17,23,6
16,23,6
16,24,6
16,25,6
16,26,6
16,27,6
16,28,6
16,29,6
15,29,6
14,29,6
13,29,6
13,28,6
12,28,6
11,28,6
11,29,6
11,29,7
11,30,7
10,30,7
10,30,10
11,30,10
12,30,10
12,29,10
13,29,10
14,29,10
14,30,10
15,30,10
15,29,10
16,29,10
17,29,10
18,29,10
18,30,10
19,30,10
20,30,10
20,30,13
20,29,13
21,29,13
22,29,13
23,29,13
24,29,13
24,28,13
24,27,13
24,26,13
24,25,13
24,24,13
24,23,13
24,22,13
23,22,13
23,21,13
23,20,13
23,19,13
23,18,13
22,18,13
22,17,13
22,16,13
21,16,13
21,15,13
20,15,13
20,14,13
20,13,13
20,12,13
21,12,13
22,12,13
22,13,13
22,14,13
23,14,13
23,13,13
23,13,14
24,13,14
24,12,14
23,12,14
22,12,14
21,12,14
20,12,14
20,11,14
20,10,14
19,10,14
18,10,14
17,10,14
16,10,14
15,10,14
14,10,14
14,9,14
14,8,14
14,7,14
15,7,14
16,7,14
17,7,14
17,6,14
17,5,14
17,4,14
17,3,14
16,3,14
15,3,14
15,2,14
14,2,14
13,2,14
13,3,14
13,4,14
13,4,15


This post has been edited by Mordion: Sep 22 2018, 05:58 PM
Go to the top of the page
 
+Quote Post
Roland
post Sep 23 2018, 03:35 AM
Post #3


Mentor
****

Group: Members Plus
Posts: 300
Joined: 20-September 16
From: Maryland
Member No.: 8,408
referrer:Google



I usually start by teleporting from the city stairs to 21,20,4. From there, I follow your path to the chute from level 7 to level 10. I didn't know about the chute from 10 to 13 - I'll have to try that. Thanks!
Go to the top of the page
 
+Quote Post
korexus
post Sep 23 2018, 08:35 PM
Post #4


Voyager
***

Group: Members Plus
Posts: 146
Joined: 24-October 07
From: Reading
Member No.: 4,011
referrer:Google Search



Nice, but the real problem here will be overcoming the muscle memory my fingers have for navigating! It might be fewer steps, but it would be months before a new route took less time for me to follow...
Go to the top of the page
 
+Quote Post
Nudibranch
post Sep 24 2018, 02:36 PM
Post #5


Fire Master
*********

Group: Mordor MP Prog
Posts: 1,613
Joined: 19-November 04
Member No.: 71
referrer:search



After years of walking down to 15, I starting using my giant to cast Teleport, which is definitely the fastest way down. Biggest drawback is that if you get careless, it is occasionally the fastest way to 16. wallbash.gif blush2.gif

Would it be too much to ask someone to record taking these routes and upload it to youtube?


--------------------
I would have started with lasers. Eight o'clock. Day one.
Go to the top of the page
 
+Quote Post
Mordion
post Sep 24 2018, 10:22 PM
Post #6


Vagabond
**

Group: Members Plus
Posts: 101
Joined: 30-September 07
Member No.: 3,924
referrer:The Super Seer



QUOTE (Nudibranch @ Sep 24 2018, 10:36 AM) *
After years of walking down to 15, I starting using my giant to cast Teleport, which is definitely the fastest way down. Biggest drawback is that if you get careless, it is occasionally the fastest way to 16. wallbash.gif blush2.gif

Would it be too much to ask someone to record taking these routes and upload it to youtube?


I would but I can't make it to 15 yet. smile.gif

Go to the top of the page
 
+Quote Post
Danjen
post Sep 25 2018, 07:55 AM
Post #7


Veteran
********

Group: Mordor MP Prog
Posts: 1,467
Joined: 25-May 07
From: Canada
Member No.: 3,498
referrer:Decklin's Domain



How did you get the data for the routes? Like did you manually plug the numbers into an array, or did you read the files from the game directly?
Go to the top of the page
 
+Quote Post
Mordion
post Sep 25 2018, 06:01 PM
Post #8


Vagabond
**

Group: Members Plus
Posts: 101
Joined: 30-September 07
Member No.: 3,924
referrer:The Super Seer



QUOTE (Danjen @ Sep 25 2018, 03:55 AM) *
How did you get the data for the routes? Like did you manually plug the numbers into an array, or did you read the files from the game directly?


I loaded the map data from mdata11. The specs are on the wiki. Then I wrote a search algorithm to find a path. I cut some corners by assuming everything costs one step. I’d like to do one with varying costs so that I could find paths that use ethereal portal but only if it saves more than X steps.

One quirk of the algorithm is that it finds the shortest path to every square of the dungeon from a single start point. Or, with the reverse path function, the path from every square of the dungeon to a specific point. By generating both I could then search the dungeon for two squares on opposite sides of a wall with a big gap in cost and cut it out. But this doesn’t generalize to multiple shortcuts.

I’ll see about uploading a binary but right now it’s Mac only.
Go to the top of the page
 
+Quote Post

Reply to this topicStart new topic
1 User(s) are reading this topic (1 Guests and 0 Anonymous Users)
0 Members:

 



Lo-Fi Version Time is now: 6th December 2019 - 08:35 PM
Bridged By IpbWiki: Integration Of Invision Power Board and MediaWiki © GlobalSoft
Copyrights and Credits