Now it’s possibly that the user choice the target point 
, also the algorithm is working well.
Also now the user can choice a particular map
What is left is the possibility to choice a different heuristic function and some other options, also some little changes in the code organization.
Here are some pictures, of paths to arbitrary target points.
Finally!! my first A* succesfully test (and you can see the path in the screen ).
I made an A_star class, with a load method to read the data from a map file (created with the map maker), but this is was a test, so at the moment is only reading ‘mapa1.mpt’.
The program recongizes the beggining point of the map, and the user should click in the target block, but for the moment I just choose an arbitrary block, to see if A* was working well.
I’m performing several tests in a very ‘ugly way’:
A_star *as = new A_star();
as->Load("mapa1");as->search(180,HE_MANHATTAN);
as->draw_path();
waitForEnter();
the first parameter of the search() method, is the target block ( I manually change that value to make tests), and the second one is the heuristic function.
I must rethink the design, because I initially focus on the A* algorithm, and now that it works I will worry about the correct design of classes.
I’m closer to a first release ( I must first clean the code)
Test 1
Test 2
One last redesign before implementing A*, this time it was concecuence of a mistake in the Engines design. In particular, the Graphics engine was holding an array with the information of each square (i.e. WALKABLE), and for that reason, the Map Maker engine needed to interact with the Graphic engine to change square status. That did’t have any sense, because, Graphics engine should only deal with drawing tasks, and also another concequence would have been that the IA engine, also would have needed to communicate with the Graphic engine to get the square status, when using the A* algorithm. So, to fix this design problem, I created a new class called Block, that have several methods to store the status of each square. Then I created an array of Blocks, but this time as part of the Gameplay engine, so now, every engine that needs to know, or change the status of a Block, needs to communicate with the Gameplay engine, including the Graphic engine, that will use the methods of Gameplay to know how it will draw a square, depending of his actual status.
Now everything is ready to begin the implementation of A*. I choose not to use the implementation of the book I showed in my last post, because it was excessively “perfect”, and too much complex, and also I wanted to make my own implementation based just in the algorithm description.
A good description can be found here: A* pathfinding for beginners
I will use the STL priority_queue container for maintining the open list, and probably the manhattan distance as heuristic function.
Yes, still more SDL, ¿why?.
Because the class design is better if I make specifics classes to handle certain SDL tasks, like drawing menus, input boxes and messages boxes (well, not real “boxes”, just kinda).
If I copy/paste the code that I’m using to draw the menus, the code will get ugly, so I decided to make a class called “Engine_Graphics_GUI” with methods like: “GUI_DrawMenu”, “GUI_ShowBoxedInput”, and others, then is cleaner to use the class in this way:
void Engine_MapMaker::MainMenu(){
Engine_Graphics* EngGraph = Engine_Graphics::Instance();
Engine_Graphics_GUI* gui = new Engine_Graphics_GUI(EngGraph->getSDLsurface());
gui->setName("MapMaker");
gui->setTitle("PathFinder v0.1");
gui->setSubTitle("Welcome to the MapMaker");
gui->setPos(350,10);
gui->setPrompt("Your choice:");
gui->addOption("1- New Map");
gui->addOption("2- Load existing map");
gui->addOption("3- Exit");
std::string option = gui->GUI_DrawMenu();
//some action depended in the value of the string
}
See? that’s another method using the “Engine_Graphics_GUI” and “Engine_Graphics” classes to draw the menu. If I need to draw several menus I have to do it in the same way that above, just changing the parameters.
Similarly I implemented a method for drawing “Input Boxes” (Ok, it’s not that nice), but it works, then if I want to use the method, is really easy, just:
std::string Engine_MapMaker::SavePrompt() {
Engine_Graphics* EngGraph = Engine_Graphics::Instance();
Engine_Graphics_GUI* gui = new Engine_Graphics_GUI(EngGraph->getSDLsurface());
gui->setName("MapMaker(Save)");
gui->setTitle("Save Map");
gui->setSubTitle("File destination(max 10):");
gui->setPos(100,5);
gui->setPrompt("->");
std::string str = gui->GUI_ShowBoxedInput();
return str;
}
Again, first the parameters, and then I call the “GUI_ShowBoxedInput()”.
I have now ended almost all the SDL staff , next post MUST be about the IA of the project ( “The finder part of the PathFinder”).
I will use som of the ideas of this book:
(Programming game AI by example) by Mat Buckland
In particular chapter 5: “The secret life of graphs” and some of chapter 8: “Practical path planning”.
Some SS’s:
(redaction unchecked!)
I have been working (again) in a pathfinder “game” (is an experiment more than everything).
I redesign all the code from scratch, and it was a good idea. The code is cleaner than before, and easier to understand (before it was mess).
The progress has been very slow, in fact, everything until now has been only class design and resolve SDL issues, and the map maker is almost finished, i have then a “Path”, but lacks the “finder” ability.
First SDL issue: writing text
It was easier than i thought, thanks to “SDL_ttf”, which provide several functions to write on screen, not very well documented, but after a few hours it becomes quite easy.
I created a class called: “Engine_Graphics_TextWritter”, which provide several methods that interact wit the SDL_ttf library, like, SetFont, SetFontStyle, SetColor and obviusly a TextWrite method.
The class is not complete, i just did what i needed at the moment, and the other things remained undone.
I provided the Code (NOT RECOMMENDED FOR REAL USE), so you can learn how to use in a simple way the TTF library, and use it as an example. Then you can rewrite things you need, remove what you dont, and add the features that are left (for example, font change is not working i think, but implementation is pretty easy, i just have been lazy).
Is an extremely easy code, and the TTF functions are pretty self explanatory. Maybe in the future I will update the class to a more completed one.
Second SDL issue: text input
This wasn’t so easy as the first one. In fact my implementation isn’t working quite right yet, i mean, it works, but it can’t be easily be extended.
Follow the LazyFooProductions tutorial’s is a very good idea, in particular Lesson 23, also you might not want to write the obvious code, is boring
So, text input works basically:
Also, be carefull when the string is empty, and when trying to “delete” an empty string. I will upload my code when i fix the main issue: “I ‘m cleaning the rectangle with a Fill that has the same colour than the background”, i should be able to receive an sprite or a color, but now i’m receaving just a color. It works for me, but is ugly.
Also, I made an Update method inside the TextInput class, is not complete yet (again!), but it should receive as a parameter a boolean indicating if we must make an Update and a constant number indicating the kind of update (UpdateRect or Flip).
I used this in my main engine graphics, because sometimes I don’t need to update after drawing (imagine drawing several things).
That’s all, I will update the classes with better design, and add the methods that aren’t complete yet.
And the pathfinder…
You can see there the map maker…now I can start concentrating in the “Finder” part, more logic and less SDL for a while
(redaction not checked yet)
One of the fastest ways of calculating prime numbers between 2 and N, is based on the Sieve of Eratosthenes, an ancient algorithm with O((nlogn)(loglogn)), this is useful for lots of ACM problems where fast pre calculation of prime numbers is needed (i.e. factorizing, weird prime properties). This algorithm is often teach in elementary school, because of his simplicity, and kids can compute primes between 2 and 100 in a almost funny and fast way.
void Eratosthenes(long n) {
long p, j, i;
a[1] = 0;
for (i=2; i < n; i ++)
a[i]= 1;
p = 2;
while (p*p <= n) {
j = p*p;
while (j <= n) {
a[j] = 0;
j = j+p;
}
do {
p=p+1;
} while (a[p]==0);
}
}
This implementation is one of the simplest ones, fast enough (it can be even faster) and works nice.
I wont explain the algorithm, since wikipedia will explain it better than me, so you can check it HERE. Basically you will end with an array ‘a[]‘ with size N, and a[i] ==1 if ‘i’ is a prime number, otherwise a[i]==0.
As you can see this is an algorithm with a simple, easy and short implementation, but is very very useful, and may, with some modification used to factorizing, have an array with just prime numbers, and many more.
In the Programming Challenges book, a nice prime factorization algorithm is presented, not the fastest way, but you can easily compute the factorization of 2^31 -1 really fast.
This algorithm is also very intuitive, and easy to renember.
The ACM algorithm:
prime_factorization(long x)
{
long i; /* counter */
long c; /* remaining product to factor */
c = x;
while ((c % 2) == 0) {
printf("%ld\n",2);
c = c / 2;
}
i = 3;
while (i <= (sqrt(c)+1)) {
if ((c % i) == 0) {
printf("%ld\n",i);
c = c / i;
}
else
i = i + 2;
}
if (c > 1) printf("%ld\n",c);
}
With this two algorithms, i think is possible to solve lots of prime numbers related problems, just by modifying some of the steps or processing the results.
“Summation of primes”, and “Factovisors” (among others), are easy to solve with these two algorithms in mind.
The useful qsort function
Why to write a new complex and maybe inefficient function for sorting arrays (of any type), if we can use qsort? Honestly i didn’t knew about the existence of this until i learned it in the Programming Workshop, and i was amazed of how easy it was and how useful it can be.
You can find the documentation anywhere (man qsort if you are in linux), so i’ll show you some examples and how you can use this function.
void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) );
that’s the function signature, it may look strange, but isn’t hard at all.
As you can see the presence of void*, tell us that it can sort any kind of arrays (int, char, struct arrays), same with the compare function.
The first argument is a pointer to the first element of the array, the second is the number of elements that the array has, the third argument is the size of each of the elements of the array (e.g. sizeof(array[0])), and the last one is the compare function, i’ll talk about that now.
The compare function must have the following signature:
int comparator ( const void * elem1, const void * elem2 );
As i told you before, that allow us to use any data type, since it receives as parameters two pointers to elements type-casted as void*. You should then cast the parameters to some data type and compare them. The function should return negative is elem1 < elem2, positive if elem1 > elem2 or zero if elem1 == elem2 (obviously based on the criteria you used in the compare function).
Consider this simple example:
int compare(const void* a, const void* b)
{
return *(char*)a - *(char*)b;
}
So if we want to compare elements in a string, the two parameters will be pointer to an element, that means, a char* pointer. That’s way we have to cast the pointers that initially are passed as void* to char* (i.e (char*)a ), then we are able to reach the value of the element by using the * operand, so as you might see if the value of a is greater than b function will return a positive number, and so on if it is less or equal than b.
char wordA[100];
/*get data into wordA*/
qsort(wordA,strlen(wordA),sizeof(wordA[0]),compare)
/*now wordA is sorted in ascending order*/
You obviously can do the same with an array of numbers, just change the casts to int*.
Multi field sorting
Now, what if we want to sort a structure with several fields, and we have many criteria, with different priorities??
Lets take the following example (based on Contest scoreboard problem).
We have to output the teams sorted by their score, and the score is equal to the problems that each team has solved, but if two teams have the same score, then the submit time is considered, including the penalties for getting Wrong Answers. If still two teams have the same time, they are displayed based on their team number.
So we have here three criteria with different priorities:
It isn’t trivial to make this kind of sorting without qsort, we might have to go through the array several time to make sure that we have considered the three criteria.
With qsort is easy, you just need to consider this in the compare function, and qsort will do the rest.
Lets assume our structure is:
struct PtjeTotal{
int eq;
int probs;
int time;
};
So we have eq (team number), probs (number of solved problems) and time (total time with penalties), and we want to sort an array already fill with data with the criteria we discuss before.
All that you need is:
int comparaDatos(const void *equipoA,const void *equipoB)
{
struct PtjeTotal *A = (struct PtjeTotal *) equipoA;
struct PtjeTotal *B = (struct PtjeTotal *) equipoB;
.
if( A->probs > B->probs)return 1; /*first criteria, number of solved problems*/
else if(B->probs > A->probs)return -1;
.
if(A->time time )return 1;/*second criteria, total time*/
else if( B->time time )return -1;
.
if(A->eq eq )return 1;/*third criteria, team number*/
else if(B->eq eq)return -1;
.
return 0; /*they are exactly equal*/
}
the dots are not part of the code, i had problems trying to make a blank line inside a code tag
That’s all!, as you can see, first we compare the number of solved problems, if they are equal nothing will be returned yet, so it moves into the next if-else, and again we compare, but this time the total time, if they are still equal nothing will be returned and we move into the last if-else, were we check the team number, they probably will be different (depending on problem statement), so it will return who is the greater based on the three criteria, or zero if they are exactly equals.
As we had seen, you can have different compare functions for sorting in many ways, or a compare function that sort a structure based on different criteria, this is very useful, and make thing a lot simpler than programming all this stuff by your own.
Ok, it took me some time to understand this problem, it was kinda strange at first, so i read it again and again until i finally understood what the different numbers were, and the different possibly cases.
That was the main difficulty for me, and the second, was to successfully read the input and parse it in a efficient way, and because you don’t have a number of instructions to read, you have to read until the end of the case, that means, until EOF or until you find a blank line.
I used the technique of character by character (not the better one). I think that fgets() would have been better and easier to make (like I showed you in the more insights post), but anyway, once you have the data in your arrays just make a function that receive and process the instructions, (switch…case) and you are done!, you then realized that this problem wasn’t hard at all!, just weird.
Another fun problem, at least for me. Is not hard, i solved it in a less than an hour, but I had tons of Presentation Error! (that means, my algorithm was right, but i had some ‘\n’ or ‘ ‘ extra or missed), until finally i realized my mistake ( a ‘\n’ missed before EOF).
For this problem i wanted a short algorithm, i didn’t want to write a lot of repetitive code, so i studied for a while how the numbers “grow”, making some draws in a piece of paper, then the algorithm is almost obvious. You need to be really careful while writting the code, because all you need is a pair of loops, but some problems may appear if you don’t check that the limits, increments, array’s indexes and sizes, are right.
Then if you accomplish that, compare your output with the sample one, and check that you are exactly following the problems instructions. After that you are done.
Easy and fun problem, that looks quite cool.
This problem is funny, you don’t need to make a very efficient algorithm as you won’t usually see a Time Limit Exceeding error here.
The input is easy to understand and to read, as you already know the size of the mine field, some loops and scanf() will do the job (or any other way you like).
To solve this, i think it all depends of the function you use to compute the number of mines that are in the field, and the correct use of arrays (at the begginning i forgot to intialize them in every new case) also check if the meemory you allocate is enough (i just declare large arrays, instead of using dynamic memory allocation, i think it’s easy to implement, and if the problem doesn’t require a fully optimized algorithm, there’s no need at all).
For the output, i get a presentation error because i forgot a ‘\n’ char between cases, so check that your output is strictly as the problem says.
