Pathfinding with Landmarks

Rate this contribution

+110

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

95 Comments

CodinBot Unnamed CodinGamer

18 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!

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!

CHOPK Unnamed CodinGamer

about 2 months ago

As for me it's an interesting and unusual puzzle.

EnjoyLife Unnamed CodinGamer

about 2 months ago

Cool concept! A few issues I spotted: Typo (appears twice): "to past given test" should be "to pass the given test" - once in the Rules (Victory Conditions area) and once in the Input section describing the efficiency parameter. Statement clarity: "the absolute of the difference" is slightly awkward - should be "the absolute value of the difference." Missing constraint on efficiency range: The input specifies efficiency is a floating point number, but there's no constraint on its range (e.g. 0 < efficiency ≤ 1). This would help solvers understand what target they're working toward.

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!

mananananaaa Unnamed CodinGamer

about 4 months ago

looks interesting

k.crowly Unnamed CodinGamer

about 4 months ago

good problem

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!

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!

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!

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!

KAKAROT_MPL Unnamed CodinGamer

about 8 months ago

Ok for me. Random 40% large too much random to pass each time. But that's ok. Ready to go.

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!

Captain_Glitterbeard Unnamed CodinGamer

about 9 months ago

Looks pretty good

FireGeoff Unnamed CodinGamer

about 9 months ago

Wow really cool, but isn't this hard instead of medium ?

aCat Unnamed CodinGamer

about 9 months ago

If you know how, according to the article, you need just a few BFSs. I hoped medium is OK, but it is debatable.

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!

Delicious31415 Unnamed CodinGamer

about 10 months ago

How do you even make the source code?

aCat Unnamed CodinGamer

about 10 months ago

I write it in the IDE.

dicebias Unnamed CodinGamer

about 11 months ago

very cool! how long did you make this?

aCat Unnamed CodinGamer

about 11 months ago

This was pretty fast - like 2-3 weeks.

CodinBot Unnamed CodinGamer

about 11 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!

FNAE Unnamed CodinGamer

about 12 months ago

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

CodinBot Unnamed CodinGamer

1 year 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

1 year 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

1 year ago

I like

Delicious31415 Unnamed CodinGamer

1 year ago

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

Sascha333 Unnamed CodinGamer

1 year ago

nice

yannB123 Unnamed CodinGamer

1 year ago

i like

CodinBot Unnamed CodinGamer

1 year 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

over 1 year ago

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

vaakqi Unnamed CodinGamer

over 1 year ago

It looks really nice! Thank you for your dedication

Aotrix Unnamed CodinGamer

over 1 year ago

It looks really nice! Thank you for your dedication

robin-hood Unnamed CodinGamer

over 1 year ago

great

CodinBot Unnamed CodinGamer

over 1 year ago

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

1215 Unnamed CodinGamer

over 1 year ago

nice

Thor37115 Unnamed CodinGamer

over 1 year ago

Looks great !

CHIKI_ Unnamed CodinGamer

over 1 year ago

noice

Andrii_Semeniuk Unnamed CodinGamer

over 1 year ago

Good

top0329 Unnamed CodinGamer

over 1 year ago

Great!

m0fix Unnamed CodinGamer

over 1 year ago

well done!

CodinBot Unnamed CodinGamer

over 1 year 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

over 1 year ago

Great work!

Claralicious Unnamed CodinGamer

over 1 year ago

great !

faizan_q Unnamed CodinGamer

over 1 year ago

Great!

smacd Unnamed CodinGamer

over 1 year ago

nice

CodinBot Unnamed CodinGamer

over 1 year 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

over 1 year ago

nice

DoYouEvenFlask Unnamed CodinGamer

over 1 year ago

nice

piotrekfolt Unnamed CodinGamer

over 1 year ago

Nice

CodinBot Unnamed CodinGamer

over 1 year 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

over 1 year ago

Good work!

Hentai_Kame02 Unnamed CodinGamer

over 1 year ago

awsome

Jasper_Boticario Unnamed CodinGamer

over 1 year ago

Nice

Vilo554321 Unnamed CodinGamer

over 1 year ago

nice

Caputolan Unnamed CodinGamer

over 1 year ago

nice

czev Unnamed CodinGamer

over 1 year ago

nice

Sarangilo_Arcian Unnamed CodinGamer

over 1 year ago

great

IamToshiro Unnamed CodinGamer

over 1 year ago

Great

branoow Unnamed CodinGamer

over 1 year ago

Hello, i love you puzzle, great work!

aCat Unnamed CodinGamer

over 1 year 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

over 1 year 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

almost 2 years 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

almost 2 years 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

over 1 year 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

almost 2 years 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

almost 2 years 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

almost 2 years ago

All suggestions applied. Thank you.

Wontonimo Unnamed CodinGamer

almost 2 years 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

almost 2 years 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

almost 2 years 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

almost 2 years ago

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

aCat Unnamed CodinGamer

almost 2 years 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

almost 2 years 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