3/pathfinding.dm at master · ceojac/3 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
pather

	var/path[]

	New()
		var/newworld[world.maxx][world.maxy]	// Creates a list with dimensions = to the world.
		path = newworld


	proc
		generate()
			for(var/map/path/p)
				path[p.x][p.y] = 1


		get_path(ax, ay, bx, by)
			var/start 	=	new/list("x" = ax, "y" = ay)	// Starting coordinates
			var/end		=	new/list("x" = bx, "y" = by)	// Ending coordinates (destination)
			var/potential[] = path							// Potential paths.  This will contain all the paths found.
			var/final[]										// Final Path from A to B

			/*	Idea for final path.  Saving them when the best path is found.  This will save long-term resources
				ie: Settal to Southshores.

				Without Saving

					Step 1, get_path() from Settal to Southshores
					Step 2, process best path, with however many failed potentials
					Step 3, finally find the final
					Step 4, direct unit along path

				With Saving

					Step 1, find_path() from Settal to Southshores. (see note)
					Step 2, if it exists, direct unit.
							If not, see 'Without Saving'

						note:
								Saving paths would save the starting coordinates, and then a list between them.
								find_path() would take in starting coordinates and return the path if found


				Idea for directing units: Sending a text string (or list?) of dirs to step in order to move from A to B.
				While they move, if they are distracted, they store their last coordinate on the path and last location
				in the string (or list?) and then walk_to() their coordinate to return following directions.

				Another idea is generating all of the path info from every location to every adjacent location, at startup.

			*/

			var/x,y		// x,y coords for the current location of the pathfinder

			x = ax
			y = ay

			if(path[x][y] == 1) // If the starting location is a path
								// We continue on and begin looking for our route!
				potential[x][y] = 1

				if(path[x+1][y] == 1)
					potential[x+1][y] = 1

				if(path[x-1][y] == 1)
					potential[x-1][y] = 1

				if(path[x][y+1] == 1)
					potential[x][y+1] = 1

				if(path[x][y-1] == 1)
					potential[x][y-1] = 1

				if(x == end["x"] && y == end["y"])

					// This is where we generate the final list based off of what we've found.

					return


	/*
		Layman's Terms.

			Step 1, Determine starting and ending location
			Step 2, Calculate a path from A to B
					This will be done by looping through a list of paths until the end is reached

					** Currently, this assumes they are connected by a path, but logic can be added
					to return that no path could be found, in which case the NPC could spit a bunch
					of debug info back to the server, so the developer can fix the problem.

			Step 3, once the path is found, generate the final list
					This will be done by removing uneccesary entities from the list.

					Algorithm?  Maybe this could be done automatically when one direction fails?

			Step 4, generate a string of dirs from A to B.