A* algorithm bypass obstacles

I have this maze. The blue nodes represent start and end of the maze. The red nodes are obstacles that can't be bypassed.
I have an A-star algorithm that gets me to the end from the start.
What i now want to do is allow x number of obstacles to be bypassed to get me to end as fast as possible. How can i develop the A-star algorithm to implement this feature?

Attached: maze.png (791x1024, 48K)

This is how my algoritthm bypasses this maze at the moment. It cannot move diagonally by the way.

Attached: maze.png (791x1024, 51K)

Good question but I legit recommend asking on Stack Overflow instead. People here can't program for shit.

This is my desired output

Attached: maze.png (791x1024, 51K)

Yeah staying away from stack overflow for as long as possible, maybe some smart code wizard visits my thread

A breadth first algorithm shouldgive you the shortest path by modeling it as a graph

The block count is the same tho, at least in this specific layout.

Do your own homework. Sage

Yeah fug just noticed that, hope it isn't confusing

Will look into this, thanks

literally just count how many obstacles it goes through instead of disallowing movement through obstacles. just exit that branch if the number of obstacles is greater than allowed obstacles

Shouldn't a-star already handle that? Its informed by the weights of each node right? So it should pick the lowest cost.

What do you mean by exiting that branch? Thanks for the response, i think i understand what you mean though

it does. But then it moves though all of the obstacles and not x number of obstacles

just end that path. realistically though this would be done by disallowing movement into obstacles if traversedObstacles == x

Oh, i have tried this approach but it didn't work for me, probably just my bad code thats causing it not work though lol

that only works for dfs or bfs which have significantly greater time complexity

what could work is to do N+1 searches in parallel - each of which allows only {0..N} obstacles to bypass. Pick the lowest distance field to progress from across all.
There is some optimization such as starting with N=0 and copying the state on bypassing next obstacle (one bypasses, other can't). However this can still have giant memory requirements for big N.

mind explaining why? i dont see why you cant just store the number of encountered obstacles and then only allow movement into nonobstacles once the obstacle limit is reached

In terms of Dijkstra you just compute two shortest path distances to each vertex - one without obstacle skipping and one with a skip.
Let f(u,v) be the usual shortest path distance and g(u,v) the shortest path distance with exactly one skip.
Let s be the start vertex.
If you know f(s,u), then the neighbours v of u have f(s,v)

Imagine having 2 ways into some field - let's say 37 steps with 2 bypasses and 61 steps with 0 bypasses. Which one do you assign? In scenario where the only possible path is through thus field and you then need all bypasses to reach the destination then taking (37,2) prevents ever reaching the destination. Simple modified Dijkstra shouldn't work here.

The "simple" solutions here either work only for one obstacle or will give you suboptimal results.
The only sensible way of doing this is by modeling the inherent state (number of skipped obstacles) within the graph (obviously a directed graph, because you can't go from 1 skip to 0). So when you move from free space into an obstacle, it's an one way edge which is connected to duplicates of every vertex, except with different state - a different "world". Your graph stops becomes 3 dimensional (x, y, number of skipped obstacles).
I hope I made it clear because I can't be bothered to type out anything more on my phone.

This user is right. You have to put "number of obstacles skipped" inside your state