Pathfinding Analysis

General
#1

Hi everyone,
I am more or less a novice in programming(My highest league in a multiplayer is Silver :frowning:) so please give a link if you think that this is a stupid question.

So my question is related to pathfinding algorithms, so you have a width into height map, and given a starting position on that map, you want to find the longest potential path to a given location without crossing over your previously crossed points.

What I have tried:
Using Python3, I used classes and Objects to stoe the graph and attempted to ccompute all such possible paths, but it kept getting timed out.
Is there any way that I can do it in python? I am not as familiar in any other language.

Thanks, Tej

#2

Longuest path is a NP problem ( https://en.wikipedia.org/wiki/NP_(complexity) ). No matter how hard you try, for a big enough map, you’ll timeout.

So, if you can’t compute all possibles paths, you have to compute some of these paths. A simple Monte Carlo ( https://en.wikipedia.org/wiki/Monte_Carlo_algorithm ) can do the trick.

1 Like
#3

Using classes you built by yourself is slow in Python.
You should use built-in classes like list, dict…

1 Like
#4

Thanks
will study the Monte Carlo

#5

Thanks, will attempt a full rewrite

#6

don’t beat yourself up. Silver league is already a nice achievement.

#7

Thanks, will not be so pessimistic :slight_smile:

#8

If this post is related to ocean of code. My advice is that you shouldn’t focus that much into the perfect path finding. Rather just aim for an ok path finding(there were some discussions about it here https://www.codingame.com/forum/t/ocean-of-code-moving-strategy/168160/13) and focus on spotting the ennemy to destroy him asap before you reach 0 life points.

#9

I havent joined ocean of code yet, I will attempt the spring contest(Not good enough yet :frowning:) I was rather focussing on this for platinum rift so as to conquer the highest number of zones.