More A* improvements

As you might know I’ve written quite a lot of articles on the A* algorithm.

This week I was contacted by Roman Kazakov (fourfor[AT]hotmail.com). He had a look at my previous A* articles and came up with a number of ways to speed up my latest version even more! Unfortunately he doesn’t have a blog, so he asked me to publish his enhancements here, so that everyone can use them. So I’ll forego the rest of this introduction and let the man speak.

(Note: the following quote is the last unedited part of an e-mail of Roman Kazakov).

Hi Roy, my name is Roman Kazakov and I am Russian guy, but live in Latin America. My Spanish is perfect, but my English is “so so”, I hope you understand me. :) I am not a professional programmer. This is just my hobby from university. And as “free lancer” I work with VS 2008 C# + DevXpress + SQL Server 2008.
I would like to present you my optimization for you program AStar. Oh, by the way, my game is 2D, and this example is in 2D dimension, but this version will by work and 3D too and more faster.
Here is code of FindPathReversed:

 private static BreadCrumb3 FindPathReversed5Final(bool[,] worldBlocked, Point2D start, Point2D end)
        {
            // Here we dont use the class Poin2D. It is bad idea use Class just for two int values (X Y)
            List<BreadCrumb3> openList2 = new List<BreadCrumb3>(256);
            BreadCrumb3[,] brWorld = new BreadCrumb3[worldBlocked.GetLength(0), worldBlocked.GetLength(1)];
            BreadCrumb3 node;
            int t1, t2;
            int tmpX, tmpY;
            int cost;
            int diff;
            t1 = worldBlocked.GetLength(0);
            t2 = worldBlocked.GetLength(1);
            BreadCrumb3 current = new BreadCrumb3(start.X, start.Y);
            current.cost = 0;

            BreadCrumb3 finish = new BreadCrumb3(end.X, end.Y);
            brWorld[current.X, current.Y] = current;
            openList2.Add(current);

            while (openList2.Count > 0)
            {
                //Find best item and switch it to the 'closedList'
                current = openList2[0];
                openList2.RemoveAt(0);
                int position = 0;
                cost = openList2.Count;
                do
                {
                    int left = ((position << 1) + 1);
                    int right = left + 1;
                    int minPosition;

                    if (left < cost && openList2[left].cost < openList2[position].cost)
                    {
                        minPosition = left;
                    }
                    else
                    {
                        minPosition = position;
                    }

                    if (right < cost && openList2[right].cost < openList2[minPosition].cost)
                    {
                        minPosition = right;
                    }

                    if (minPosition != position)
                    {
                        node = openList2[position];
                        openList2[position] = openList2[minPosition];
                        openList2[minPosition] = node;
                        position = minPosition;
                    }
                    else
                    {
                        break;
                    }

                } while (true);

                current.onClosedList = true;

                //Find neighbours
                for (int i = 0; i < 8; i++)
                {
                    tmpX = current.X + surrounding2[i, 0];
                    tmpY = current.Y + surrounding2[i, 1];
                 //   tmp = current.position + surrounding[i]; //This is is a really slow!!!
                    /*if (tmp.X >= 0 && tmp.X < t1 &&
                tmp.Y >= 0 && tmp.Y < t2 &&
                !worldBlocked[tmp.X, tmp.Y])*/
                    if (tmpX >= 0 && tmpX < t1 &&
             tmpY >= 0 && tmpY < t2 &&
             !worldBlocked[tmpX, tmpY])
                    {
                        //Check if we've already examined a neighbour, if not create a new node for it.
                        if (brWorld[tmpX, tmpY] == null)
                        {
                          //  node = new BreadCrumb3(tmpX,tmpY);
                           // brWorld[tmpX, tmpY] = node;
                            brWorld[tmpX, tmpY] = node = new BreadCrumb3(tmpX, tmpY); // This is more fast!
                        }
                        else
                        {
                            node = brWorld[tmpX, tmpY];
                        }

                        //If the node is not on the 'closedList' check it's new score, keep the best
                        if (!node.onClosedList)
                        {
                            diff = 0;
                            if (current.X != node.X)
                            {
                                diff += 1;
                            }
                            if (current.Y != node.Y)
                            {
                                diff += 1;
                            }
                            cost = current.cost + diff + ((node.X - end.X) * (node.X - end.X)) + ((node.Y - end.Y) * (node.Y - end.Y));//node.position.GetDistanceSquared(end);

                            if (cost < node.cost)
                            {
                                node.cost = cost;
                                node.next = current;
                            }

                            //If the node wasn't on the openList yet, add it
                            if (!node.onOpenList)
                            {
                                //Check to see if we're done
                               // if (node.Equals(finish)) // This is slow too!!!
                                if (node.X == finish.X && node.Y == finish.Y)
                                {
                                    node.next = current;
                                    return node;
                                }
                                node.onOpenList = true;
                                openList2.Add(node);

                                int position2 = openList2.Count - 1;

                                int parentPosition = ((position2 - 1) >> 1);

                                while (position2 > 0 && openList2[parentPosition].cost > openList2[position2].cost)
                                {
                                    node = openList2[position2];
                                    openList2[position2] = openList2[parentPosition];
                                    openList2[parentPosition] = node;
                                    position2 = parentPosition;
                                    parentPosition = ((position2 - 1) >> 1);
                                }

                            }
                        }
                    }
                }
            }
            return null; //no path found
        }

Comments:
Look in my screenshots which i made it for you. For looking performance I used ANTS Performance Profiler 5.2. This is a great “stuff”!
Also you can use your benchmark. Check the file zip attached. There is all source and information for compiled.
Comments about code:
The general “thing” in programming in C# is do not use Obj Class and etc. where really dont need to use that! The best performance is just “Value type” and List<>
Array, maybe Struct.
In my optimized code I deleting class MinHeap where T : IComparable. Why?! Because is really slow, and I dont know why. Also use class Point2D just for 2(3) types X and Y( and Z), it was a bad idea. And many thing more. Looked my code and you understand which changes I made it. I hope this is help you. And please put this optimization on you wonderful web page http://roy-t.nl, as New Optimized Version A*.
When we made the games, we looking for more faster algorithm and code. This article will be help a many people as us.
We made the games of our dreams…

Roman also included a couple of pictures to show the speed gain of his code
Original code (by me)

New implementations (by Roman)

27
Jun 2010
COMMENTS 3 Comments

Re: Writing a book ????

Some of you might look a but strange at the title, it is the exact same title as TheZman’s latest blog post.

His post got me to think again about a project I’d like to start on *(Oh god, this makes me think of the oh so many projects that I want to start on!). Writing a book? It takes quite a lot of courage and determination to write a good technical book. Hell I know that I haven’t yet acquired the technical skills for it. (Maybe I haven’t even mastered English  enough yet). So obviously I’m not think about writing a technical book.

However I would like to write a book for people who are not into (game-) programming or maybe even games in general. I would like to introduce readers to a kind of ‘ambiance’ that gives us developers such a comfortable feeling when developing for games. I would like to tell people how difficult game programming is, what games really are (in my opinion that is). And what some games with attention to detail, and attention to the real world, can bring to people.

Hell it would be a book worthy of a game-evangely. Of course there should be added technical parts, but the book I’d like to write would also contain parts that you could take a good sit for and read for pleasure.

This however brings me to how to actually release a book. Of course I could just put it up here as a pdf and be done with it, but that’s not really what I had in mind. Publishing a game, getting your name on there somewhere is also something that could thrive me into making a  book.

Oh well, first back to spell and style checking my blog posts I guess. But maybe I could do a small primer someday, say 50 pages, and see what people think. (And count the number of mistakes, to see how long it would take to correct a full book…).

21
Jun 2010
CATEGORY

Blog, Personal

COMMENTS 2 Comments

Thoughts: automatic tests and user interfaces

Lately I’ve been working on a rather large project (software web shop that automatically adds and updates products). The customer required that a large part of the software was automatically tested. We accomplished this by using PHPUnit (somewhat quirky, but it got the job done). However there was one big problem.

The problem

The web shop was built with the Zend Framework in true MVC fashion. This meant that it was very easy to write unit tests for the model. However the model wasn’t that complex, just a bunch of queries and some massaging of the fetched data. The most interesting things happened in the views and we had no clue how to test the views automatically. Because we had a hard deadline, and didn’t have time to fully dive into this problem, one of our testers committed himself to test all the views every day. This was feasible because we didn’t have too many views.

Current approaches

Automatically testing user interfaces is hard, especially in web languages. In a C# or Java application you can at least fill in text boxes and ‘press’ some buttons via code, although this will require you to (temporarily) make a lot of stuff public. In web languages you don’t have this amount of direct control; the closest thing would be to write a lot of Javascript. However Javascript’s state is lost on page transitions so you’d have to write the state to a file, fetch it on the next page, continue testing there, and so on. This seems like a really big bunch of work, with not much gain. However maybe there is a framework out there, which does just this thing. Maybe you can tune it to navigate the web shop for you, however there is still another big problem.

Presentation is important

For a user interface it is very important how everything looks. In web apps a small typo can make a page totally unreadable. A possible approach would be to strictly specify where a control should appear (maybe in pixels relative to the browser’s borders). But this is not possible to check with any Javascript or any other web front-end language I know. Maybe an application can make a screenshot and compare this with a screenshot that was deemed correct? Even this approach might not work very well as this would already give an error when the text on a label was partially changed.

Possible solution

I’ve come up with the following solution so far. This is just an idea which I’ve just cooked up (and the reason for this post) but I believe that it would work. Unfortunately there is no product available on the market yet that does these things.

In my opinion a good user interface tester would test in two steps. One test focused on content correctness and one focused on visual correctness.

The content correctness test would roughly follow the following steps:

• Request a page from the server

• Fill in controls and click buttons, following a predefined ‘test path’

• Verify that returned pages contains correctly filled in elements (does the label with name label1 contain the text “hello world”?). This could be done by adding a special identifier to each control that needs to be tested. The identifier can be hidden in ‘comments’ so that even during testing the web application stays compatible with normal browsers.

For every step a screenshot is made from the render output in the most popular web browsers. If the content correctness test succeeds the visual correctness test is executed, which contains the following test.

• Record control positions and sizes by ‘scanning’ the screenshots using OCR techniques. Might be aided by cross referencing the page’s source code.

• Test if controls are inside predefined ‘control locations’. Think of setting this up by dragging rectangular boxes over a screenshot to specify where a control should approximately be.

• If a control is not entirely on the correct location calculate a badness percentage.

• If the accumulated badness percentage is too high: fail the test and generate a nice picture, clearly marking the deviations.

• Also give the tester the option to select a failed test as the new correct references. This is useful for quickly updating tests when larger parts of the interface are changed.

Of course this approach doesn’t solve all the problems of testing user interfaces. And user interfaces will also have to be checked manually once in a while. However I think an application capable of performing the above tests would be very handy. Most of the above is also applicable to non-web applications btw.

I would very much like to hear everyone’s thoughts on this. How do you currently test user interfaces, have you come up with a feasible way to test large user interfaces?

07
Jun 2010
CATEGORY

Blog, Programming

COMMENTS 4 Comments