Fastest path through maze

[Jay Dee]

I am trying to design a set of classes that calculate and return the
fastest root through a maze.

I have a class that represents a page containing text and a set of
links to other pages.

So far I have produces a class that will return the steps required to
navigate from the current page to the desired page but the process is
slow.

I understand that this is because my code is now where near optimised
and it keeps repeatedly checking the same paths over and over again.

I can not get my head around how to stop it though.

Douse anyone no of a solution or any pointers in the right direction.

Many thanks in advance for any support.

Jay Dee

public abstract class Page
{
// the collection of directly linked pages
public PageLinkList PageLinkList;
// the collection of all pages
public PageList PageList;
// uneque id of current page
public int PageNumber;

// activate seteps required to follow a direct link
public virtual void FollowLink(int linkIndex, ref Lines lines, Task
task);
// do the given lines match the current page
public abstract bool MatchLines(Lines lines);
// calculate the steps from the current page to the desired page
public List<int> StepsToPage(int pageNumber);
public List<int> StepsToPage(Page page);
private void StepsToPage(Page page, List<int> steps, int maxSteps)
{
if (this.PageNumber == page.PageNumber)
{
return;
}

if (maxSteps == 0)
{
steps.RemoveAt(steps.Count - 1);
return;
}

if (this.PageLinkList.Count == 0 || maxSteps <= 0)
{
return;
}

List<int>[] stepLists = new List<int>[this.PageLinkList.Count];

for (int i = 0; i < this.PageLinkList.Count; i++)
{
if (page.PageNumber == this.PageLinkList.LinkToPageNumber)
{
stepLists = new List<int>();
stepLists.Add(i);
}
else
{
stepLists = new List<int>();
stepLists.Add(i);
this.PageLinkList.LinkToPage.StepsToPage(page,
stepLists, maxSteps - 1);
}
}

// select the fastest path
List<int> fastestRoot = stepLists[0];
for (int i = 1; i < this.PageLinkList.Count; i++)
{
if (stepLists.Count > 0 && stepLists.Count <
fastestRoot.Count)
{
fastestRoot = stepLists;
}
}

// add the path to the return list
for (int i2 = 0; i2 < fastestRoot.Count; i2++)
{
steps.Add(fastestRoot[i2]);
}
}
}

 

[Andrew Poelstra]

I am trying to design a set of classes that calculate and return the
fastest root through a maze.

I have a class that represents a page containing text and a set of
links to other pages.

I don't understand. How are these two statements related?

 

[Patrice]

I am trying to design a set of classes that calculate and return the

fastest root (path ?) through a maze.

Hello,

I remember to have seen once a pathfinding algorithm known as A*. Try
perhaps :
http://en.wikipedia.org/wiki/A*_search_algorithm

You should find some material and perhaps even an implementation if you are
searching for game programming articles...

 

[Fred Mellender]

Hello,

I remember to have seen once a pathfinding algorithm known as A*. Try
perhaps :
http://en.wikipedia.org/wiki/A*_search_algorithm

You should find some material and perhaps even an implementation if you
are searching for game programming articles...

This problem is very suited to solving via A*. If that is not clear, use a
depth first search.
You can find a C# implementation of A* and DFS in my book (free to download)
at
http://www.lulu.com/product/download/design-patterns-for-searching-in-c#/3074608

 

[Jeff Johnson]

You can find a C# implementation of A* and DFS in my book (free to
download) at
http://www.lulu.com/product/download/design-patterns-for-searching-in-c#/3074608

404

 

[Fred Mellender]

404

Try http://sites.google.com/site/fredm/ to download my book on graph
searching in C#.

 

[Jeff Johnson]

Try http://sites.google.com/site/fredm/ to download my book on graph
searching in C#.

Thanks!

 

[Arne Vajhøj]

I am trying to design a set of classes that calculate and return the
fastest root through a maze.

I have a class that represents a page containing text and a set of
links to other pages.

So far I have produces a class that will return the steps required to
navigate from the current page to the desired page but the process is
slow.

I understand that this is because my code is now where near optimised
and it keeps repeatedly checking the same paths over and over again.

I can not get my head around how to stop it though.

Douse anyone no of a solution or any pointers in the right direction.

Many thanks in advance for any support.

I think you need to split your problem up in:
1) a solution to the mathematical problem
2) implementation in C#

Arne

 

[Family Tree Mike]

I am trying to design a set of classes that calculate and return the
fastest root through a maze.

I have a class that represents a page containing text and a set of
links to other pages.

So far I have produces a class that will return the steps required to
navigate from the current page to the desired page but the process is
slow.

I understand that this is because my code is now where near optimised
and it keeps repeatedly checking the same paths over and over again.

I can not get my head around how to stop it though.

Douse anyone no of a solution or any pointers in the right direction.

Many thanks in advance for any support.

Jay Dee

public abstract class Page
{
// the collection of directly linked pages
public PageLinkList PageLinkList;
// the collection of all pages
public PageList PageList;
// uneque id of current page
public int PageNumber;

// activate seteps required to follow a direct link
public virtual void FollowLink(int linkIndex, ref Lines lines, Task
task);
// do the given lines match the current page
public abstract bool MatchLines(Lines lines);
// calculate the steps from the current page to the desired page
public List<int> StepsToPage(int pageNumber);
public List<int> StepsToPage(Page page);
private void StepsToPage(Page page, List<int> steps, int maxSteps)
{
if (this.PageNumber == page.PageNumber)
{
return;
}

if (maxSteps == 0)
{
steps.RemoveAt(steps.Count - 1);
return;
}

if (this.PageLinkList.Count == 0 || maxSteps<= 0)
{
return;
}

List<int>[] stepLists = new List<int>[this.PageLinkList.Count];

for (int i = 0; i< this.PageLinkList.Count; i++)
{
if (page.PageNumber == this.PageLinkList.LinkToPageNumber)
{
stepLists = new List<int>();
stepLists.Add(i);
}
else
{
stepLists = new List<int>();
stepLists.Add(i);
this.PageLinkList.LinkToPage.StepsToPage(page,
stepLists, maxSteps - 1);
}
}

// select the fastest path
List<int> fastestRoot = stepLists[0];
for (int i = 1; i< this.PageLinkList.Count; i++)
{
if (stepLists.Count> 0&& stepLists.Count<
fastestRoot.Count)
{
fastestRoot = stepLists;
}
}

// add the path to the return list
for (int i2 = 0; i2< fastestRoot.Count; i2++)
{
steps.Add(fastestRoot[i2]);
}
}
}

Just my opinions, but...

1. Why would each page need to contain a list of all pages?
2. You never seem to consider whether the next step (page) is already in
the steps sent into the method. This would lead to unnecessary loops.
3. List<T> lend themselves to foreach () loops better than for () loops.
I don't know that your code is bad per se.
4. Your subject line, talking about mazes, does potential describe a
similar algorithm class. So does a traveling salesman problem though.
If you want a maze solution, show code aimed at that. If you want a
page navigation solution, use that in the title.

 

[Jeff Johnson]

3. List<T> lend themselves to foreach () loops better than for () loops.

Why? Lists sit on arrays. Indexed access to arrays is cheap, no?

 

[Family Tree Mike]

Why? Lists sit on arrays. Indexed access to arrays is cheap, no?


.

I was probably just imposing my own style on the answer. I guess I should
have said if you don't care about the index into the array so much, but
rather are just looping over the contents, the go for the foreach loop.

Mike

 

[Peter Duniho]

Why? Lists sit on arrays. Indexed access to arrays is cheap, no?

Indeed. I would say that both are equally applicable to both "foreach"
and "for". In general, I use "for" when I need an index (e.g. I'm
iterating parallel indexed collections, or I need the index for some
other specific operation besides just retrieving one element at a time,
etc.) and a "foreach" when all I need are the individual elements one at
a time.

Both looping statements work equally well for List<T> and an array.

Pete

 

[Jeff Johnson]

I was probably just imposing my own style on the answer. I guess I should
have said if you don't care about the index into the array so much, but
rather are just looping over the contents, the go for the foreach loop.

Now that I totally agree with.

 

[Jay Dee]

Hi all

Your feedback has been a grate help.

I found this link extremely helpful and I created my own csharp code
based on the information gathered

http://www.policyalmanac.org/games/aStarTutorial.htm

I apologise for the misleading title, before starting this thread I
had never heard of astar and to be honest, didn’t really no what I was
asking for.

I have learnt a lot from this, many thanks for you help.

As for the comments regarding foreach loops verses for loops, I do not
see much difference. I prefer to use “for” loops because access to the
current index is often useful especially when you want to remove, or
insert items to, from the list during the loop.

Am I correct in saying that there would be no speed/performance
improvements for or against either and that it would just be personal
preference?

I think there is still going to be issues with the following code
because it douse not stop looking for paths on roots that are already
longer than a known root. But for now it is a massive improvement on
what I had before.

Many thanks for all your input

Jay Dee


public List<Page> StepsToPage(Page toPage)
{
Page fromPage = this;
fromPage.f = 0;
fromPage.h = 0;
fromPage.pointA = null;

List<Page> finalList = new List<Page>();

List<Page> openPages = new List<Page>();
List<Page> closedPages = new List<Page>();

openPages.Add(fromPage);

while (openPages.Count > 0)
{
// find page with lowest f score
Page page = openPages[0];
for (int i = 1; i < openPages.Count; i++)
{
if (openPages.f < page.f)
{
page = openPages;
}
}

// process sub pages
for (int i = 0; i < page.PageLinkList.Count; i++)
{
Page subPage = page.PageLinkList.LinkToPage;
if (subPage == toPage)
{
int g = 10;
int h = 0;
int f = page.f + g + h;

subPage.f = f;
subPage.pointA = page;
while (subPage.pointA != null)
{
finalList.Insert(0, subPage);
subPage = subPage.pointA;
}

return finalList;
}
else if (closedPages.Contains(subPage))
{
int g = 10;
int h = 0;
int f = page.f + g + h;
if (subPage.f > f)
{
subPage.f = f;
subPage.pointA = page;
}
continue;
}
else if (openPages.Contains(subPage))
{
int g = 10;
int h = 0;
int f = page.f + g + h;
if (subPage.f > f)
{
}
continue;
}
else
{
openPages.Add(subPage);

int g = 10;
int h = 0;
int f = page.f + g + h;

subPage.g = g;
subPage.h = h;
subPage.f = f;
subPage.pointA = page;
}
}
closedPages.Add(page);
openPages.RemoveAt(0);
}

return finalList;
}