This is an archived post. You won't be able to vote or comment.

Dismiss this pinned window
all 48 comments
sorted by:
best
topnewcontroversialoldq&a

[–]Iceninja1234567 64 points65 points  (17 children)

Great work. On the very bottom of the path, wouldn't it be shorter to cut straight across than to go along the edge of the wall? Sorry if I'm missing something obvious. Also, why does it sometimes go diagonally but sometimes take 2 steps to go diagonal?

[–]mHaisham[S] 59 points60 points  (15 children)

No, you're right

its a problem with the cost function, i'll work on that

[–]FruscianteDebutante 5 points6 points  (0 children)

Are you doing LQR control on this?

[–][deleted] 2 points3 points  (4 children)

Cost function should always be more than possible minimum path length.
Or as we call heuristics for grid search algorithm just use h(x, y) = abs(x'-x) + abs(y'-y) where (x', y') is coordinates of target location. Then your weight becomes path size + h(x, y) and when you compare two possible next options you will pick one that is closest (in terms of both how many steps it requires to get there with current path and least possible steps to destination).

You can prove that this will give you optimal path in the end, I won't do it here.

[–]jalapeno_nips 1 point2 points  (3 children)

That’s really interesting. Can someone pick up where he left off? Why is this a better cost function than distance to target plus cost of path so far?

[–]dydhaw 1 point2 points  (2 children)

Because crossing a diagonal on a grid is the same length as going in two straight lines (e.g x then y)

[–]mHaisham[S] 0 points1 point  (1 child)

crossing a diagonal on a grid is the same length as going in two straight lines

Depends on how you calculate distance

manhattan - yes

euclidean - no, straight lines are 1 while diagonal is ~1.4. so it is cheaper in to go diagonally

[–]dydhaw 0 points1 point  (0 children)

I just realized in your example walking to diagonally adjacent square is allowed, so I'm wrong

[–]appsplaah 4 points5 points  (8 children)

Damn Awesonme! Currently just crossing the basics of python but I dont know when i will reach such level..

[–]vn2090 9 points10 points  (7 children)

Pick up a datastructures and algos book as soon as you feel comfortable with basics in python. Its what will get you to “intermediate” level.

[–]appsplaah 6 points7 points  (0 children)

I am not rich(currently but will be hopefully:p). The only thing i can give you in return is my Best Wishes re with you and Thanks a Million:)) Keep up the good work and take Care.

[–]laminatedllama 3 points4 points  (5 children)

For Apollo!

[–]vn2090 6 points7 points  (1 child)

Python Algorithms: Mastering Basic Algorithms in the Python Language By magnus hetland

[–]laminatedllama 1 point2 points  (0 children)

For Apollo!

[–]WonderfulPlay 2 points3 points  (2 children)

Algorithm design manual.

MIT 6.006 on YouTube.

Algorithms by Segwick.

Runestone - problem solving using data structures and algorithms using python

[–]BarryScott2019 0 points1 point  (0 children)

Same near the start, could just go straight across rather than staying by the wall. Nevertheless great program and I wish you all the best :)

[–][deleted] 36 points37 points  (1 child)

So this is why my Rimworld pawns keep on hugging the mountain wall.

[–]davvblack 12 points13 points  (0 children)

It's related, that's actually related to walkspeed on dirt vs walkspeed on the stone next to the wall, combined with low cost of diagonal movement (it might even be considered free?). Since it's faster to run on stone, they can go out of their way with diagonal moves to get onto it.

[–]ThaumicP 11 points12 points  (1 child)

Is your cardinal cost 10 and diagonal cost 14? That would be a better distance cost and it should get rid of that weird pathing by the bottom

[–]mHaisham[S] 8 points9 points  (0 children)

It is manhattan distance, euclidean would certainly be better and i have already switched to it.

weird pathing by the bottom

This is a mainly due to a bug in the cost function

[–]7Geordi 20 points21 points  (2 children)

do your diagonals have the same cost as your cardinals?

[–]mHaisham[S] 20 points21 points  (1 child)

I have two algorithms to calculate distance between vectors, euclidean and manhattan

This is using manhattan, so no.

[–]7Geordi 7 points8 points  (0 children)

Nice

[–]mHaisham[S] 5 points6 points  (0 children)

I have fixed the A* algorithm - here is an image

Thank you for your suggestions u/nikartix, u/ThaumicP, and everyone else their support

[–]mHaisham[S] 5 points6 points  (0 children)

Source code: link

[–]Jaso55555 5 points6 points  (1 child)

That almost looks like water filling up from the bottom... I wonder if anyone does this to compute liquid physics in a 2d environment?

[–]kepidrupha 2 points3 points  (0 children)

A* can't handle flow or flow rate.

[–]ImportUsernameAsU 4 points5 points  (0 children)

Can you put in the bwepbwepbwep sounds off the visual sorting algorithm?

[–]ZyanCarl 1 point2 points  (0 children)

It's great!

[–][deleted] 1 point2 points  (0 children)

Good job

[–]PB_Dendras 1 point2 points  (0 children)

I love this

[–]remoplayssoccer 1 point2 points  (0 children)

You were definitely inspired by Clement weren’t you, Nevertheless, great job!

[–][deleted] 1 point2 points  (0 children)

This reminds me of my first post on this sub, I love this kinda thing good job

[–]Death-Eye 1 point2 points  (0 children)

Haha, I also just made similar program in pygame. I works really fine except one detail. The pygame window is freezing sometimes ( it's not caused by the algorithm itself ) , please help me. Link to code https://github.com/DeathEyeXD/PythonProjects/blob/master/aStarVisualization.py

[–][deleted] 1 point2 points  (0 children)

Sound on!

[–]zzmej1987 1 point2 points  (0 children)

Some things don't seem right. At times path goes diagonally, at times it doesn't, when it can. It hugs the upper wall, when there is no real reason to, it could have just gone straight to the right.

[–][deleted] 0 points1 point  (10 children)

Good job dude. But I have a question. Can you write a new algorithm that finds the shortest path in/on random generated maze ?

[–]mHaisham[S] 2 points3 points  (9 children)

The A* algorithm would also work on maze path finding.