Removing the obstacle that yields the best path from a map after A* traversal

Posted by David Titarenco on Stack Overflow See other posts from Stack Overflow or by David Titarenco
Published on 2010-03-22T02:18:56Z Indexed on 2010/03/22 2:21 UTC
Read the original article Hit count: 511

Filed under:

c++

|

a-star

|

algorithm-design

I traverse a 16x16 maze using my own A* implementation. This is exactly what my program does:
http://www.screenjelly.com/watch/fDQh98zMP0c?showTab=share

All is well. However, after the traversal, I would like to find out what wall would give me the best alternative path. Apart from removing every block and re-running A* on the maze, what's a clever solution?

I was thinking give every wall node (ignored by A*), a tentative F-value, and change the node structure to also have a n-sized list of node *tentative_parent where n is the number of walls in the maze. Could this be viable?

© Stack Overflow or respective owner

Related posts about c++

Which C++ book shold I get between "C++ Primer" vs "C++ Primer Plus"

as seen on Stack Overflow - Search for 'Stack Overflow'
I want to learn C++ by using Vim and MinGW as compiler. I'm interesting at "C++ Primer (4th Edition)" and "C++ Primer Plus (5th Edition)" but I don't know how about it different. It has no book store that I can review those books, so I want to know, what is the different between those book and which… >>> More
C++ : C++ Primer (Stanley Lipmann) or The C++ programming language (special edition)

as seen on Stack Overflow - Search for 'Stack Overflow'
I have a Computer Science degree (long2 time ago) .. I do know Java OOP but i am now trying to pick up C++. I do have C and of course data structure using C or pascal. I have started reading Bjarne Stroustrup book (The C++ Programming Language - Special Edition) but find it extremely difficult esp… >>> More
I need help on my C++ assignment using MS Visual C++

as seen on Stack Overflow - Search for 'Stack Overflow'
Ok, so I don't want you to do my homework for me, but I'm a little lost with this final assignment and need all the help I can get. Learning about programming is tough enough, but doing it online is next to impossible for me... Now, to get to the program, I am going to paste what I have so far. This… >>> More
Managed c++ std::string not accessible in unmanaged c++

as seen on Stack Overflow - Search for 'Stack Overflow'
In unmanaged c++ dll i have a function which takes constant std::string as argument Prototype : void read ( const std::string &imageSpec_ ) I call this function from managed c++ dll by passing a std::string. When i debug the unmanaged c++ code the parameter imageSpec_ shows the value correctly… >>> More
The Definitive C++ Book Guide and List

as seen on Stack Overflow - Search for 'Stack Overflow'
After more than a few questions about deciding on C++ books I thought we could make a better community wiki version. Providing QUALITY books and an approximate skill level. Maybe we can add a short blurb/description about each book that you have personally read / benefited from. Feel free to debate… >>> More

Related posts about a-star

Star Wars Roguelike Combines Star Wars and Old School ASCII Adventures

as seen on How to geek - Search for 'How to geek'
Mashup ASCII-based adventuring, Star Wars, and some sweet light saber sound effects, and you’ve got this old-school in-browser adventure game: Star Wars Roguelike. Play a Jedi or Sith and move about the ASCII world with simple keyboard commands. You’re not going to be blow away by the… >>> More
Open GL stars are not rendering

as seen on Game Development - Search for 'Game Development'
I doing Nehe's Open GL Lesson 9. I'm using SFML for windowing, the strange thing is no stars are rendering. #include <SFML/System.hpp> #include <SFML/Window.hpp> #include <SFML/Graphics.hpp> #include <iostream> void processEvents(sf::Window *app); void processInput(sf::Window… >>> More
GNU Smalltalk package

as seen on Ask Ubuntu - Search for 'Ask Ubuntu'
I've installed the GNU Smalltalk package and can get to the SmallTalk command line with the command 'gst'. However, I can't start the visual gst browser using the command: $ gst-browser When I try, this is what I get: peter@peredur:~$ gst-browser Object: CFunctionDescriptor new: 1 "<0x40488720>"… >>> More
remove a:hover using javascript (not using jquery... don't ask)

as seen on Stack Overflow - Search for 'Stack Overflow'
I thought this would be pretty simple.... Basically, it's a 5-star rating system. When a user clicks, for example, three stars... I want to freeze those three stars right where they're at. I've been trying to simply remove the hover for the a href so it stays what it was at... maybe that's not the… >>> More
How to get star query optimization in SQL Server 2005

as seen on Stack Overflow - Search for 'Stack Overflow'
I have a star schema but SQL Server 2005 always uses the clustered indexes to access a table. What parameters do I have to set to enable this optimization. According to http://blogs.msdn.com/sqlqueryprocessing/archive/2007/04/09/how-to-check-whether-the-final-query-plan-is-optimized-for-star-join… >>> More