54
u/Nicksil Mar 24 '18
Nice. What's the code look like?
57
u/boijunior Mar 24 '18
The code is about 400 lines long not including all the classes and other functions it references.
39
u/Nicksil Mar 24 '18
OK. May we see it?
71
u/boijunior Mar 24 '18
Without dumping 3,000+ lines of code it will be very confusing to follow; however, I am happy to explain the general principle behind it.
It starts by drawing a line between the character and the goal.
Then takes all objects it intersects with and takes the corners of the objects and path finds to these (trying to find a route around the object).
It repeats this process of path finding to every possible "node" (a corner of an object or the goal) until it checks every possible outcome and finds a path between the two points.
It eliminates paths if there is a shorter distance to a point, if the path so far is shorter than a path found to the goal, or if there is a collision between the object and a line. There is also a few other ways it eliminates paths but you hopefully understand the general principle.
109
u/Nicksil Mar 24 '18
The code is about 400 lines long
...
Without dumping 3,000+ lines of code
I don't understand.
Also
it will be very confusing to follow
Not necessarily for everyone here; some of us can manage.
96
u/boijunior Mar 24 '18
https://gist.github.com/BoiJr/39574461b98be0777865cad9099ba1dc
Hopefully this helps more. It is all mildly annotated.
108
u/hemenex Mar 24 '18
If you use more
while a: if not b: continue cinstead of
while a: if b: cyou will lose most of that crazy indentation.
25
25
u/IamNickMead Mar 24 '18
This. Learning this trick changed my code for the better and I've never looked back. This and closures
13
u/loneraver Mar 25 '18
I think flake8 committed suicide.
13
u/13steinj Mar 25 '18
The worst part is the tabs. I mean I'm not some fanatic, but I legitimately thought this was a lot of empty code on mobile before scrolling all the way right.
3
u/tylerthehun Mar 24 '18
Interesting. I never knew you could use
continuewithwhile. It's like I've discovered usingelsewithforall over again!2
1
u/WiggleBooks Mar 25 '18
This seems really interesting! But I'm having trouble understanding what the advantage is?
How does it work?
0
61
u/arachnivore Mar 24 '18 edited Mar 25 '18
I have a few pointers:
Your algorithm is very simple. Usually in Python, you can express an algorithm with about as many characters as it takes to describe the algorithm in English.
If I'm getting this right, the basic idea is:
1) find all the objects that lie on the line between the destination and the source 2) A: If there are no objects, a path has been found B: find all the corners of those objects that have line-of-sight to the destination 3) treat those corners as destinations and repeat 1-3 4) return the shortest pathI understand it's a little more complicated than that, but not excessively so. You can add caching and pruning etc. after you get the basic version going and it should even be fairly concise.
If the only state you maintain between runs is memoization, then you want a function, not a class.
Comments are O.K., but it's usually better to flesh-out your algorithm by breaking up the work into yet-to-be-written helper functions:
def find_path(source, destination, map): obstacles = intersections(source, destination, map) if not obstacles: return [source] possible_paths = [] for vertex in vertices(obstacles, destination, map): possible_paths.append(find_path(source, vertex, map) return [destination] + min(possible_paths, key=path_length)Now you have to define some helper functions:
intersections,vertices, andpath_lengthI would highly recommend going on YouTube and watching any videos you can find featuring Raymond Hettinger.
I usually discourage using recursion in Python because its easy to cause a stack overflow especially if you're often using other people's code and you don't know (or shouldn't have to know) if their implementations also use recursion. Thankfully it's fairly easy to turn a recursive function into an iterative one. You simply make your own 'stack' object within the function to keep track of the state of previous iterations:
def find_path(source, destination, map): paths, completed = [[destination]], [] while paths: path = paths.pop() dest = path[-1] obstacles = intersections(source, dest, map) if not obstacles: completed.append(path + [source]) else: paths.extend(path + [v] for v in vertices(obstacles, dest, map)) return min(completed, key=path_length)Learn and use pep8 and the google code style guidelines and try to stick to them (but don't be super anal about it).
Keep names, especially local variable names, simple. If you have a
ChessGameclass just call it Chess, we know chess is a game. IfChesshas achess_boardattribute, call itboard.ChessGame.chess_boardis obnoxious. If a word appears once on the path to something, that's usually enough. If you have:
from boijuniors_games.boijunior_chess import BoijuniorChessBoardyou're making puppies cry.
This is a good talk on coding style.
That is all. ...for now.
Edit: Here's a few tips about helper functions and methods:
The interfaces of most functions and methods should be fairly short. If they get to long, it's usually a hint that you need a class that bundles up a bunch of related stuff into one object:
intersections(source, dest, map) # could be map.intersections(source, dest)Your IDE will complain as you make up functions that don't exist. If you're anything like me, you'll find those red squiggles extremely distracting, so you'll stub out the functions like so:
def path_length(path): passA better approach is to always make sure your stubbed out functions will remind you that you haven't finished writing all your code:
def path_length(path): raise NotImplementedError()Now if you've stubbed out a million functions and forgot to actually implement some, they will tell you instead of quietly returning a None and causing all sorts of confusion.
Also, it's generally a good idea to put meat before potatoes. That means, put your main
find_pathfunction at the top of the module and all the helper functions below because when I read your code, I can guess that you know how to find the length of a path. That's usually not what I'm interested in. If I'm really digging in to how your algorithm works (or more likely: where the bug is) I can read thepath_lengthimplementation, but don't make me scroll through all your helper functions to get to the meat of your code.8
6
u/barburger Mar 25 '18
The comment above contains great advices. If you were just scrolling through I advise reading it again.
1
35
u/justphysics Mar 24 '18
As a recommendation I give out frequently:
You have a main block of you logic loop that begins
for i in range(0,len(self.paths) ):You should get used to using the python builtin "enumerate". Essentially enumerate will iterate over any sequence that supports iteration (like a list) and return two items on each iteration - the index of the item and the item from the sequence.
So your main for loop is really saying "I want to iterate over self.paths and do some logic based on one or more of the items it contains and I need to know the index of each item ...". Rather than making a range object to get something with the same length of self.paths, just iterate over self.paths directly:
for idx, path in enumerate(self.paths): # first iteration will have idx=0, path=self.paths[idx] # of course you can still use `i` instead of idxLikewise you'll probably want to do the same thing for you loop over self.nodes:
for j, node in enumerate(self.nodes): # first iteration starts at j=0, node=self.nodes[j]At a quick glance, you could clean up a lot of your for loops this way.
9
u/boijunior Mar 24 '18
Good tip!
6
u/wataf Mar 24 '18
Also if you rename the gist to PathFinder.py we will get syntax highlighting in github :)
2
u/Bilbino Mar 25 '18
Ooh, thanks for that tip. In the past, when I’m iterating through a list and need to know the index and contents, I iterate through a range the same length of the list (for the index), and then use somelist[i] (for the contents). This will definitely simplify things!
1
1
u/warbird2k Mar 25 '18
Check out Effective python. It has a lot (59) of tips on writing better code. Use of enumerate in loops is one of them.
1
1
u/barafyrakommafem Mar 25 '18
for i in range(0,len(self.paths) ):You can just write
for i in range(len(self.paths)):4
u/justphysics Mar 25 '18
Yes, but if you ever need to do self.paths[i] why not just use enumerate?
1
u/barafyrakommafem Mar 25 '18
You should of course use enumerate, but that was not what I was commenting on.
16
u/muntoo R_{μν} - 1/2 R g_{μν} + Λ g_{μν} = 8π T_{μν} Mar 24 '18
Why does your code have an
if inside a
for inside a
for inside an
if inside an
if inside an
if inside a
for inside an
if inside an
if inside a
for inside a
while?To quote Linus Torvalds:
"...if you need more than 3 levels of indentation, you're screwed anyway, and should fix your program."
6
1
u/Taxi-guy Mar 24 '18
Rookie here, what are some ways to reduce the amount of indentation I use in my code? (i.e. to "fix" my heavily indented program)
3
u/Atrament_ Py3 Mar 24 '18
Functions, guards ( if / continue / break). You also need to make all this insensitive to context (no dependencies to globals)
1
u/muntoo R_{μν} - 1/2 R g_{μν} + Λ g_{μν} = 8π T_{μν} Mar 27 '18
See this recent HackerNews post: Avoid Else, Return Early (2013)
Essentially,
Functions
Return statements
Single responsibility
0
Mar 25 '18
[deleted]
2
u/Taxi-guy Mar 25 '18
Thanks for all the information! I'll go back and look at some of my code, keeping these points in mind. I'm pretty bad about having 5 or 6 levels of indentation in some of my code :O
-2
u/boijunior Mar 24 '18
I guess in this case I'm going to have to respectfully disagree... I am by not an expert but there is a decent amount of logic that goes into the code. It could be cleaner with ways shown above but I think all the if statements are necessary. The for loops are excessive but I don't think there is an alternative that is objectively different. Cleaner syntax yes but the principle remains.
12
u/muntoo R_{μν} - 1/2 R g_{μν} + Λ g_{μν} = 8π T_{μν} Mar 24 '18
But there is a massive amount of logic that goes into programs far, far more complex than this in all domains -- including scientific applications such as this. They manage to keep indentation (and cyclomatic complexity) to a minimum. In fact, this becomes more and more important for programs of larger complexity!
Could you imagine if e.g. the tensorflow backend was written with 10000 nested levels and 100000 lines all in one function?
2
u/boijunior Mar 24 '18
I see your point. I guess in this case the only way to reduce indentation I see is to "spread" the code out more by placing each loop into its class but I don't see them as removable. I will look back over it.
→ More replies (0)1
1
Mar 24 '18
I've seen professional applications with stupid long loops with crazy amounts of indentation. At a certain point, it's harder to maintain and change anything.
116
u/b1ackcat Mar 24 '18
"mildly annotated". Comments every single line.
Lol. Good stuff, I just thought that was funny
1
u/shaggorama Mar 25 '18
Barely scrolling, I'm seeing nesting 12 levels deep. You should break this up into more self-contained functions.
-1
0
Mar 24 '18
[deleted]
21
Mar 24 '18
Everyone seems to be pretty constructive so far?
9
u/Rodot github.com/tardis-sn Mar 24 '18
I think that's just an aspect of the Python community. A lot of other programming communities aren't as forgiving.
10
u/boijunior Mar 24 '18
Okay. What is the best way for me to upload it? Reddit messes with the formatting.
Also the additional 2,600 lines are for misc things like drawing the images to the screen. I will omit those
13
3
u/Nicksil Mar 24 '18
If you want to post to reddit, you can do a select-all, then indent all by four spaces, select all again and post that. It's just a quick way of formatting for correct display on reddit.
Otherwise, off the top of my head:
There are many others, I'm sure.
2
u/LifeHasLeft Mar 24 '18
He said “400 lines not including ...”
1
u/Nicksil Mar 24 '18
Correct, which is why I was only asking to have a look at the implementation. OP ultimately posted it and it came in at just under 350 lines.
1
u/TalphaLL Mar 24 '18
OP, how does one run the code?
0
u/Bilbino Mar 25 '18 edited Mar 25 '18
I have not run it personally, but I would assume you’ll need to install Python and whatever libraries the code uses (I know you at least need to install pygame, not sure on others. If you’re a windows boy, after installing python, go to the command prompt and type “pip install [lib_name]” The library name should be the same as what it says after ‘import’ in the code.) Go into python idle (go to the start menu and type idle, “Python IDLE” should come up), and make a new python file. Paste the code into the file, and run it. Although, OP talked about leaving some stuff out of the code, so it might not work.
1
u/Exodus111 Mar 24 '18
So wait, how does it know when its time to start raycasting again once its tracking around an object?
It seems from the gif, it repeates the raycast once its arrived at any corner, at a set distance from the corner. If this is true, wont this be a major issue if the objects are more advanced polygons, with more than 4 corners?
2
u/boijunior Mar 24 '18
For my game I couldn't perform the whole pathfinder multiple times in the same frame or else it would cause a drop in fps so it's spread out over multiple frames. So it continuously would check all nodes and the pathfinder stops when it exceeds the allotted time in ms. And then starts back up the next frame for the allotted time. More advanced polygons never cause an issue outside of being more taxing as they are more complex.
1
u/arachnivore Mar 24 '18
The general algorithm (I think) goes like this:
1) draw a line from the destination to the current location 2) find all the object that line intersects 3) find corners of those objects that have line of sight to the destination 4) treat those corners destinations and repeat steps 1-4 until you've found the shortest path.1
u/UD_Gama_Reigh Mar 25 '18
If it takes into account the corners of the objects, why dont the lines cut closer to said objects to save some distance? Is there some form of padding around the objects?
2
u/boijunior Mar 25 '18
It isn't shown very well in the gif I suppose but the character is somewhat large and couldn't cut straight to the corner because of his width.
19
u/thinknirmal Mar 24 '18
Does it take the shortest path though? Doesn't seem to.
18
u/boijunior Mar 24 '18
AFAIK it does. It might lose some space due to not doing things like rounding corners etc. that's still a wip... also is does check for size so for instance the last path doesn't cut through the smaller space.
9
u/Ur_Legit Mar 24 '18
I was thinking the same thing. OP should look into Dijkstras algorithm for finding the shortest path
39
u/Gnlfbz Mar 24 '18
I have several years of professional experience doing open area routing. Dijkstras actually wouldnt work here since there aren't any preexisting paths to route on. Once a network has been created you can use a routing algorithm like Dijkstras or even better a bidirectional A*.
Even if this isn't the absolute shortest path it is amazing work. I is kinda like a depth first search through open space. I would love to see the code.
9
Mar 24 '18
It looks to me like he creates a CDT (constrained delaunay triangulation) or it's equivalent voronoi diagram. Then, he probably uses visibility graphs and Dijkstras algorithm to find the shortest center point to center point to center point path, or perhaps a funnel method.
Recommended reading if you want to implement an awesome algorithm like this can be found in a research paper here. You should be able to find it for free access online by the title or author:
Navigation Meshes and Real-Time Dynamic Planning for Virtual Worlds
Marcello Kallmann (University of California Merced)
4
u/thinknirmal Mar 24 '18
A cluster of midpoints between known boundaries gives you a vague list of predefined waypoints. A* can easily then build on top of that.
2
u/Peragot Mar 24 '18
Could you use the corners of the obstacles (+ start and end points) as nodes of the graph and then run Djikstra?
1
u/XkF21WNJ Mar 25 '18
That should work. If you change direction in the middle of a 'road' then there is a shorter path where you cut that corner. The only place where this isn't possible is at the corners of obstacles. So except for corners of obstacles the path should be straight, hence Dijkstra or A* on those corners should be sufficient.
2
u/nanodano Mar 25 '18
There is only one example in there that looks like it might not be the shortest route, but if it's taking in to account the size of the object and where it can fit, it might not squeeze through, and then the route it chose does make sense.
7
Mar 24 '18
Explain more about the game. It looks interesting. What does it do? What is the idea?
20
u/boijunior Mar 24 '18
Right now I'm just working on the mechanics behind the pathfinder. So the white boxes would be things like buildings, lakes, etc. The game will be a top down RPG with point and click mechanics kinda like Starcraft or age of empires.
4
Mar 24 '18
Nice. Let me know when you are done with this. I am new to python. Are you using pygame?
9
u/boijunior Mar 24 '18
Yes I am using Pygame 3.4.4
3
u/videobrunch Mar 24 '18
are you intending to publish it ? Or is it just a hobby game
4
u/boijunior Mar 24 '18
It's a hobby game but I also intend to publish it. I have to look at the logistics of doing it through Steam or something similar.
3
u/videobrunch Mar 24 '18
It’s very cool - I just started working with pygame recently. Love to see what people are doing with it - Keep us updated!
3
u/hansdieter44 Mar 24 '18
So you are essentially using raytracing for path finding? Did you come up with that algorithm?
Could you reflect the rays if they hit something white?
Looks awesome.
10
u/boijunior Mar 24 '18
I don't think so but I'm not really in the coding industry so I may be understanding ray tracing wrong from a quick google search... It works by "drawing" a line to each "node" from each node (a node is a corner, the start point, or the goal) and checking whether there are any collisions. It repeats this process for every node. It eliminates paths through various ways to speed up the code. Any successful paths I compare the distances to find the shortest one. I did come up with the path finder.
3
Mar 25 '18
Drawing a line and checking if there is a collision is essentially ray tracing, just so you're aware.
1
u/overwashed Mar 25 '18
Looks cool. Seems tho there’s a shorter path on the last path it drew...? Why is that?
5
3
u/NikEy Mar 25 '18
I don't know, I'm not an expert in pathfinding algorithms, but this doesn't look very efficient to me. It looks cool and is certainly innovative, but it cannot be very fast. On a large map the calculation time must get exponentially larger
1
u/ryeguy Mar 24 '18
Cool demo. What made you come up with your own algorithm instead of using something standard like A*?
3
u/boijunior Mar 24 '18
I don't like the idea of trying to incorporate others work into my own because then I have more trouble debugging. I also don't really understand A* or Dijkstras in free space.
21
Mar 24 '18
[removed] — view removed comment
13
u/matchu Mar 24 '18 edited Mar 24 '18
I don't think they were saying "I don't understand the algorithms", but rather "I don't understand how they would apply to free space rather than a predetermined network of points". Discretization is a nontrivial piece of the puzzle!
1
1
u/wieschie Mar 24 '18
You can tell me if I'm off here, but A* is a "pretty good, pretty quickly" search, right? Once it finds a a path to a goal, using some heuristic to hopefully choose good moves, it terminates.
His search seems to be nearly comprehensive - it explores all paths to the goal by some method (while pruning cycles) and then chooses the objective best.
1
u/krikun98 Mar 25 '18
A* can find the optimal path with the right heuristic. Without one it's just Dijkstra, and that's been mathematically proven to find the shortest path.
This, however... Without looking at the code I can't be sure, but OP himself doesn't say it's the shortest path.
1
u/nanodano Mar 24 '18
Very cool! Those lines are draw in real time then? You aren't slowing it down as a visual effect? Since that is a really performance intensive operation, that is something you might consider moving in to a C++ module at some point to improve the performance.
3
u/boijunior Mar 24 '18
It is not real time it's slowed quite significantly.
1
u/nanodano Mar 25 '18
Cool! It also looks like it's built in a way where you could modify the 'resolution' of the pathfinding to dynamically trade off accuracy for speed if there are a large number pathfinding at once.
4
u/keypusher Mar 24 '18
You should think about creating a library out of this. Make a python package and set it up on pypi. I would be happy to help if you need.
1
u/bigpigfoot Mar 25 '18
if u gave it a system that required it to go backwards somehow in order to find the shortest route, such as would be the case in a labyrinth, what would happen?
1
1
u/Arancaytar Mar 25 '18
What algorithm is this? I've never tried to do path finding in an open area; my only approach here would be to discretize it into a grid, which is probably much more expensive and restricts movement to cardinal directions.
1
1
1
0
113
u/boijunior Mar 24 '18
The first path took 23 ms, second 44 ms, 3rd 58 ms, 4th 20 ms, 5th 8 ms, 6th 15 ms, 7th 7 ms.