CODEWITHSUNDEEP
algorithm2d
Einarsson
Einarsson

Reputation: 522

Longest paths given max length

I'm need of help.

I'll try to explain as perfect as possible.

Let's say I have a 2d grid which is my "world".

The grid looks like this:

grid

The grey squares are grass. The green squares are roads. The orange squares are desert.

The blue square in the middle is my car. My car has a range limit of 5 squares. I want to find and highlight ALL the squares I can reach with max range or less.

Driving across a grey square costs 1 range. Nothing fancy. However, Driving across a green square gives you +0,5 range. Which means, if the first 2 squares you drive through are green, your max range is suddenly 6. Driving across an orange square gives you a -0,5 range penalty. This means if the first 2 squares you drive through are orange, you only have a max range of 4.

So basically, driving to a square, costs you 1 range, but depending on the square it can give you extra range or an lesser range.

Scouting all paths considering the bonuses. Would make the most outer reach of my car looking like this: enter image description here

So yes, I want a way to find all the squares marked with black borders, and all the ones inside of them. So that all squares within my max range are highlighted.

Long question, but how do I achieve this?

I've looked into breadth and depth first etc but since I can take several routes through the same square I cant mark it as "visited" the first time and then never return to it?

Help on this would be greatly apprechiated.

Thanks for reading all the way down here.

/E

Upvotes: 1

Views: 172

Answers (1)

Nikita Rybak
Nikita Rybak

Reputation: 68006

You could represent your model a bit easier, all in terms of cost and not bonuses.

  1. You have 5 days to travel.
  2. Driving through one square of the grass takes 1 day.
  3. Driving through one square of the desert takes 1.5 days.
  4. Driving on the road takes 0.5 days for each segment.

Now, you have a simple graph and you can find all locations not farther than 5 days away with Dijkstra's algorithm.

Upvotes: 9

Related Questions