Pathfinding with Landmarks

Rate this contribution

+82

Work In Progress

The creator is still working on the contribution. Feel free to add remarks and suggestions to improve the contribution before the approval process!

Comments

71 Comments

CodinBot Unnamed CodinGamer

10 days ago

I hope you received enough feedback from the community to improve your contribution. Once you have made the necessary updates, publish your contribution!

domainexpansioninfinitevoid Unnamed CodinGamer

13 days ago

Not bad, feels like the difficulty should be hard instead of medium

CodinBot Unnamed CodinGamer

about 1 month ago

I hope you received enough feedback from the community to improve your contribution. Once you have made the necessary updates, publish your contribution!

CodinBot Unnamed CodinGamer

about 2 months ago

I hope you received enough feedback from the community to improve your contribution. Once you have made the necessary updates, publish your contribution!

Ernestini Unnamed CodinGamer

about 2 months ago

I like

Delicious31415 Unnamed CodinGamer

about 2 months ago

Don't know how to do it but I like it

Sascha333 Unnamed CodinGamer

about 2 months ago

nice

yannB123 Unnamed CodinGamer

about 2 months ago

i like

CodinBot Unnamed CodinGamer

about 3 months ago

I hope you received enough feedback from the community to improve your contribution. Once you have made the necessary updates, publish your contribution!

CodinBot Unnamed CodinGamer

about 4 months ago

I hope you received enough feedback from the community to improve your contribution. Once you have made the necessary updates, publish your contribution!

wdd-dev Unnamed CodinGamer

about 4 months ago

It looks really nice! Thank you for your dedication

Aotrix Unnamed CodinGamer

about 5 months ago

It looks really nice! Thank you for your dedication

robin-hood Unnamed CodinGamer

about 5 months ago

great

CodinBot Unnamed CodinGamer

about 5 months ago

I hope you received enough feedback from the community to improve your contribution. Once you have made the necessary updates, publish your contribution!

1013 Unnamed CodinGamer

about 5 months ago

nice

Thor37115 Unnamed CodinGamer

about 5 months ago

Looks great !

CHIKI_ Unnamed CodinGamer

about 5 months ago

noice

Andrii_Semeniuk Unnamed CodinGamer

about 5 months ago

Good

top0329 Unnamed CodinGamer

about 5 months ago

Great!

m0fix Unnamed CodinGamer

about 5 months ago

well done!

CodinBot Unnamed CodinGamer

about 6 months ago

I hope you received enough feedback from the community to improve your contribution. Once you have made the necessary updates, publish your contribution!

tgarmenliev Unnamed CodinGamer

about 6 months ago

Great work!

Claralicious Unnamed CodinGamer

about 6 months ago

great !

faizan_q Unnamed CodinGamer

about 6 months ago

Great!

smacd Unnamed CodinGamer

about 7 months ago

nice

CodinBot Unnamed CodinGamer

about 7 months ago

I hope you received enough feedback from the community to improve your contribution. Once you have made the necessary updates, publish your contribution!

Fidefix Unnamed CodinGamer

about 7 months ago

nice

DoYouEvenFlask Unnamed CodinGamer

about 7 months ago

nice

piotrekfolt Unnamed CodinGamer

about 7 months ago

Nice

CodinBot Unnamed CodinGamer

about 8 months ago

I hope you received enough feedback from the community to improve your contribution. Once you have made the necessary updates, publish your contribution!

kaspernewb Unnamed CodinGamer

about 8 months ago

Good work!

Hentai_Kame02 Unnamed CodinGamer

about 8 months ago

awsome

Jasper_Boticario Unnamed CodinGamer

about 9 months ago

Nice

Vilo554321 Unnamed CodinGamer

about 9 months ago

nice

Caputolan Unnamed CodinGamer

about 9 months ago

nice

czev Unnamed CodinGamer

about 9 months ago

nice

Sarangilo_Arcian Unnamed CodinGamer

about 9 months ago

great

IamToshiro Unnamed CodinGamer

about 9 months ago

Great

branoow Unnamed CodinGamer

about 9 months ago

Hello, i love you puzzle, great work!

aCat Unnamed CodinGamer

about 9 months ago

I have conducted additional tests regarding the reasonability of each threshold, and as a result, several of them have been lowered. Unless something unexpected happens, I assume the puzzle is finished.

CodinBot Unnamed CodinGamer

about 9 months ago

I hope you received enough feedback from the community to improve your contribution. Once you have made the necessary updates, publish your contribution!

CodinBot Unnamed CodinGamer

about 10 months ago

I hope you received enough feedback from the community to improve your contribution. Once you have made the necessary updates, publish your contribution!

ggrn Unnamed CodinGamer

about 10 months ago

Hi, a very nice puzzle. For the test 'Empty, tiny, 8 landmarks' discussed below I get an average score of 0.0865 (efficiency of 1 on the first round (path length/number of closed nodes 9/9), 0.818 on the second round (9/11) and 0.777 on the third (7/9). The score is calculated using your suggested set of landmarks: 10 10 1 1 10 1 1 10 6 6 5 2 2 5 10 6, where the expected average is 0.78. I am wondering if the difference in the scores is not implementation specific (I am using C++). I noticed that there are a lot of nodes with the same minimal f-value in the priority queue and if I pick one over the other I get different scores. If this is the case, it might be a good idea to add another rule to compare nodes with the same f-value.

aCat Unnamed CodinGamer

about 9 months ago

Putting the same values hardcoded: PASSED! Average ALT efficiency required 0.667, achieved 0.780. The same output provides the same score regardless of the language.

aCat Unnamed CodinGamer

about 11 months ago

Thanks to the suggestions, I've made some global changes: - The number of tests was increased for most of the maps - to give them a better estimate of the average case. - Nearly all efficiency thresholds were modified - by running my algorithm several times with different seeds and choosing the lowest score. - The game summary now contains the required/achieved score.

5DN1L Unnamed CodinGamer

about 11 months ago

Rules * Please fix the typo: assumming => assuming. * Suggest to change EITHER "open (passable) tiles" to "open tiles (passable)" OR "wall tiles (impassible)" to "wall (impassible) tiles" for consistency. Constraints * Please change "numLandMarks" to "landmarksNum" for consistency with other sections and the default code. Thanks.

aCat Unnamed CodinGamer

about 11 months ago

All suggestions applied. Thank you.

Wontonimo Unnamed CodinGamer

about 11 months ago

I haven't read the paper, but my instinct would be to place the landmarks randomly then using a simulation push them away from eachother using floodfill as the metric. Those landmarks that can floodfill more can move to give up space, and those who can't reach much via floodfill can move to take up more space. Iterate 20 times and a local optimum should be reached. But that probably isn't the paper

aCat Unnamed CodinGamer

about 11 months ago

It's actually close to one of the proposed algorithms, but yours is more complicated :P. (maybe better In efficiency, but more computationally expensive.)

Wontonimo Unnamed CodinGamer

about 11 months ago

I really like this puzzle. I'm probably not going to try solving it because it requires research, but I do hope it gets approved! I too have been thinking of adding more A* like puzzles, so it's nice to see you made one

aCat Unnamed CodinGamer

about 11 months ago

There will be more pathfinding puzzles soon :-). New semester and new lecture is coming ^^'

aCat Unnamed CodinGamer

about 11 months ago

Please help me adjust the proper efficiency thresholds for each test - this puzzle is not meant to be hard and tiring. The current values are based on my solution, the "farthest landmark selection" algorithm, plus some tricks for handling multiple connected components.

cedricdd Unnamed CodinGamer

about 11 months ago

Hi, I'm currently using a basic "Farthest-Point Sampling" to select the landmarks, just selecting the point the farthest from all the previously selected points and I'm already starting to fail with 'Empty, tiny, 8 landmarks', I'm assuming you're not using any 'tricks' on that one. Shouldn't you give the pair of start/end points used to test the efficiency so we can check if our landmarks will pass and be able to change them if not.

ABOUT US CAREERS PRIVACY FAQ BLOG

The #1 tech hiring platform

SCREENING INTERVIEWING