|
I am trying to develop a dynamic pathing algorithm for a game (all text) and running into an issue of finding the shortest path when all the edges(connectors) are the same cost or weight.
The algorithm below will capture all the rooms from start to finish, but the issue is sorting it out to find the shortest distance to the finish, perhaps new algorithm is needed? Thanks in advance for any assistance.
public void findRoute(ROOM_INFO startRoom, ROOM_INFO destinationRoom)
{
Dictionary<ROOM_INFO, bool> visitedStartRooms = new Dictionary<ROOM_INFO, bool>();
Dictionary<ROOM_INFO, bool> visitedStopRooms = new Dictionary<ROOM_INFO, bool>();
List<string> directions = new List<string>();
startQueue.Enqueue(startRoom);
destinationQueue.Enqueue(destinationRoom);
visitedStartRooms.Add(startRoom, true);
visitedStopRooms.Add(destinationRoom, true);
string direction = "";
bool foundRoom = false;
while (startQueue.Count != 0 || destinationQueue.Count != 0)
{
ROOM_INFO currentStartRoom = startQueue.Dequeue();
ROOM_INFO currentDestinationRoom = destinationQueue.Dequeue();
ROOM_INFO startNextRoom = new ROOM_INFO();
ROOM_INFO stopNextRoom = new ROOM_INFO();
if (currentStartRoom.Equals(destinationRoom))
{
foundRoom = true;
break;
}
else
{
foreach (string exit in currentDestinationRoom.exitData)
{
stopNextRoom = extractMapRoom(exit);
if (stopNextRoom.Equals(startRoom))
{
visitedStopRooms.Add(stopNextRoom, true);
foundRoom = true;
break;
}
if (stopNextRoom.mapNumber != 0 && stopNextRoom.roomNumber != 0)
{
if (!visitedStopRooms.ContainsKey(stopNextRoom))
{
if (visitedStartRooms.ContainsKey(stopNextRoom))
{
foundRoom = true;
}
else
{
destinationQueue.Enqueue(stopNextRoom);
visitedStopRooms.Add(stopNextRoom, true);
}
}
}
}
if (foundRoom)
{
break;
}
}
foreach (string exit in currentStartRoom.exitData)
{
startNextRoom = extractMapRoom(exit);
if (startNextRoom.Equals(destinationRoom))
{
visitedStartRooms.Add(startNextRoom, true);
foundRoom = true;
break;
}
if (startNextRoom.mapNumber != 0 && startNextRoom.roomNumber != 0)
{
if (!visitedStartRooms.ContainsKey(startNextRoom))
{
if (visitedStopRooms.ContainsKey(startNextRoom))
{
foundRoom = true;
break;
}
else
{
startQueue.Enqueue(startNextRoom);
visitedStartRooms.Add(startNextRoom, true);
}
}
}
}
if (foundRoom)
{
break;
}
}
}
}
|
|
|
|
|
I did not study your code, and unfortunately you did not describe your algorithm at all, nor did you provide a reference to whatever inspired you.
I do know the normal approach would be something along these lines:
- provide a storage for "distance from starting point" to each node;
- initialize to "infinite" (well, zero would be fine too as long as you read that as infinite!);
- now start walking around from the starting node, using a "breadth first" scheme; this means you go one step away from the starting point in all possible ways, you keep track of all the possible points at this distance (that needs a collection, say a list, it does not need an ordered collection such as a queue), and also set the distance to 1 for all the nodes you can reach in that one step.
- now repeat for all the nodes you collected as having distance 1, then 2, then 3, etc.
- however, for each node N that you can reach from node P in one step, make distance(N) equal to distance(P)+1 only if it does not already have a smaller value.
- now the first time you reach the destination, you are sure to have reached it in the minimal number of steps. And by looking at the distance values, you can trace one way back to the starting point without needing any memory or any trials, just walk the way the distance decreases by one on every step.
To my knowledge there isn't any superior algorithm, so the only thing you can do for performance is come up with a decent implementation!
|
|
|
|
|
Sorry Luc, your right I should have just explained what I was trying to do with the algorithm instead of the code.
I am pretty much doing what your saying except for the keeping track of distance.
Algorithm goes like this:
1. Place Start and End rooms into a start queue and end queue.
2. Enter a while loop with a condition not to leave while there is at least a Start or End Room loaded or that the destination is found.
3. I dequeue the room and iterate through each exit the room has and mark it as visited and load that room into the queue.
4. Repeat step 3 until I reach my destination or run out of rooms.
|
|
|
|
|
That sounds pretty similar, I see it is breadth first; I'm not sure you also are getting the best route, as it seems you don't have permanent storage (the steps taken are being removed from the queues, aren't they?).
|
|
|
|
|
|
Dijkstra's is considering too many possibilities: when all the edge costs are equal, the first solution found is bound to be the cheapest, no need to continue and investigate all the remaining routes.
|
|
|
|
|
Luc Pattyn wrote: when all the edge costs are equal, the first solution found is bound to be the cheapest, no need to continue and investigate all the remaining routes.
The best way might be to implement a generalized algorithm like Dijkstra's algorithm, you never know what might come up  .But for the sake of simplicity it is good to use Breadth First Search (BFS) in such a case as you outlined in your answer. However, in a game application the graph might not always contain edges of equal cost, anyways since the OP wants a specific algorithm for a graph with edges of equal cost then BFS suffices.
“Be at war with your vices, at peace with your neighbors, and let every new year find you a better man or woman.”
|
|
|
|
|
This is an easy read if you are familiar with set notation.
http://planning.cs.uiuc.edu/node4.html
I have an unfinished project on the shelf which attempts to find the shortest path through a maze by "pressurizing" the maze at the entrance and coloring-in "temperature" or "pressure" at each cell in the maze. The "coolest" or "lowest pressure" (bluest) path is the shortest solution.
Good Luck
Tadeusz Westawic
Sum quid sum.
modified 9-Jul-12 11:19am.
|
|
|
|
|
hi, my question is
if i have 3 basic colors (each made of rgb):
color1 : R:150, B:zero, G:255
color2 : R:255, B:150, G:zero
color3 : R:zero, B:255, G:150
They can be mixed using the formula :
new_color = floor(X*0.9)+floor(Y*0.1)
X and Y can be a basic color or a new color allready created by using the formula.
for example, if i want to mix color1 as main with color3 :
new_color(R,B,G) = (floor(0.9*150)+floor(0.1*0) , floor(0.9*0)+floor(0.1*255) , floor(0.9*255)+floor(0.1*150) ) = (135, 25, 244).
I need to find a way to mix the colors in order to get a desired color, for example : R:187 B:135 G:201
so far i wrote a "brute force" program which go all over the combinations of basic colors (runing for 7 days now got up to 16 mixing steps) and a bit smarter AStar algorithm (got good reults for small sequnces, letting it run for the week end...).
hope there is a smarter and faster way to solve the problem.
Btw, i code with matlab or vb.
Thanks.
|
|
|
|
|
Please do not repost questions in multiple forums. This has already been dealt with here[^].
|
|
|
|
|
sorry, only after posting it there i discovered the algorithm section.
the answer i got there is not correct.
thanks.
|
|
|
|
|
Kobi_Z wrote: new_color = floor(X*0.9)+floor(Y*0.1)
Kobi_Z wrote: new_color(R,B,G) = (floor(0.9*150)+floor(0.1*0) , floor(0.9*0)+floor(0.1*255) , floor(0.9*255)+floor(0.1*150) ) = (135, 25, 244).
Given two color's X,Y, floor(Y*0.9) + floor(X*0.1) and floor(X*0.9) + floor(Y*0.1) give different results,so physically speaking why is that so? The equation has to be commutative, mixing two colors is supposed to be commutative. Please explain why this discrepancy?
“Be at war with your vices, at peace with your neighbors, and let every new year find you a better man or woman.”
|
|
|
|
|
BupeChombaDerrick wrote: Given two color's X,Y, floor(Y*0.9) + floor(X*0.1) and floor(X*0.9) + floor(Y*0.1) give different results,so physically speaking why is that so? The equation has to be commutative, mixing two colors is supposed to be commutative. Please explain why this discrepancy?
Kobi_Z wrote: for example, if i want to mix color1 as main with color3 :...
the first color you mix is the main one.
It is a riddle some students asked at my university and I try to "solve" it because I find it interesting i dont think you should look on the physical aspect .
hope it explains any discrepancy.
Thanks.
|
|
|
|
|
Okay so in your riddle the colors are mixed in 0.9 and 0.1 proportions where the main color gets 0.9 and the next color gets 0.1?
Perhaps you would have said the formula
new_color = floor(a*X) + floor(b*Y)
where a,b are variable proportions such that a + b = 1. Mathematically correct, in your case a = 0.9 ,b = 0.1. My question is why 0.9 and 0.1,is it how it is? or 0.9 and 0.1 proportions are just for illustration purposes? I want to fully understand the riddle before i think of a solution, i'am not trying to be difficult.
“Be at war with your vices, at peace with your neighbors, and let every new year find you a better man or woman.”
|
|
|
|
|
it is a fixed formula :
new_color = floor(0.9*x)+floor(0.1*b)
"it is how it is"...
Thanks.
|
|
|
|
|
Okay i googled "color mixing riddle" and your questions here http://www.mymathforum.com/viewtopic.php?f=20&t=31242[^]
is clearer. Okay now I get the question, will see if i can think of a faster solution, will get back to you. 
“Be at war with your vices, at peace with your neighbors, and let every new year find you a better man or woman.”
|
|
|
|
|
|
mixing two colors in uneven quantities can do almost that, but then I would expect only one floor action, something like
new_color = floor(0.9*X + 0.1*Y)
as the mixing would be a continuous operation, the result may need quantisation.
|
|
|
|
|
its a given question...
i think its like that (the floor) because then mixing same color with itself decreases final most higer value by one.(mix(color1,color1) results in [150,0,254])
|
|
|
|
|
And that, while unnatural, is a clue to an upper bound on the complexity of the solution...
|
|
|
|
|
So the factors 0.9 and 0.1 are just variable proportions, well i thought they were constants as initially illustrated by the OP. Now i get it.
Thanks.
“Be at war with your vices, at peace with your neighbors, and let every new year find you a better man or woman.”
|
|
|
|
|
0.9 and 0.1 are constants.
|
|
|
|
|
Well knowing the reason why 0.9 and 0.1 are constants might have been fun. Because colors can be mixed in any proportion a,b such that new_color = floor(a*X) + floor(b*Y) where a + b = 1. But in your case it seems the colors are forced to be mixed in 0.9 and 0.1 proportions which means that the order of mixing becomes important, So you are looking for the order in which one can mix basic colors in 0.9 and 0.1 proportions, I must say that there might be no ways of solving it other than a brute force search method, the truncation operation "floor" further complicates matters when one attempts a mathematical analysis. 
“Be at war with your vices, at peace with your neighbors, and let every new year find you a better man or woman.”
|
|
|
|
|
In terms of algebra, your question is ill posed. You are in 3D space (the RGB cube). All possible mixtures of the two colors form a line segment (a whole straight line if you allow negative values of the mixing coefficients).
(In this discussion, I admit that the mixture constraint X + Y = 1 is enforced, which you didn't mention.)
Unless by coincidence, there is no reason that your third color belongs to the segment(or the line). You get a system of three equations in one unknown, usually without a solution.
To handle this we can look for the "best approximation", i.e. the mixture that will minimize the discrepancy with the desired color. Even though it is not recognized as "perceptually uniform", you can use the Euclidean distance.
In other words, you will project the desired color to the line segment by means of an orthogonal projection.
Let X C0 + (1-X) C1 be a color between C0 and C1. The vector from this point to C2 needs to be perpendicular to the direction C0C1. Hence, (X C0C2 + (1 - X) C1C2).C0C1 = 0 (. is the dot product). I.e. X C0C2.C0C1 + (1 - X) C1C2.C0C1 = 0, or X = C1C2.C0C1 / (C1C2.C0C1 - C0C2.C0C1) = - C1C2.C0C1 / C0C1.C0C1.
To restrict the solution to the range of positive coefficient mixtures, just clamp the value of X to the range [0..1].
Rather than a week of computation, this should take less than 100 nanoseconds in compiled code.
modified 19-Jun-12 2:59am.
|
|
|
|
|
Help me!
i have a problem about AND/OR Graph Search Demo.
Who can help me???
Thank you very much!
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
