Closing Credits

Formal Acknowledgements

I would like to thank first and foremost, Prof. Naresh Jotwani, my guide and mentor, who not only gave guidance on algorithm design and implementation in this project, but was also the reason for its genesis. The discussions we’ve had on the subject matter have proved invaluable in determining the direction and scope of this body of work. Not only has he acted as a technical guide, but he also provided motivational “pep-talks” whenever required.

My sincere thanks to Akshat Kumar, Arpit Dhariwal, Prashant Tholia and Prasoon Gupta for letting me usurp their PCs for my work. A special mention for Abhishek Gupta who helped out with Bryce 5.

I would also like to thank the development team (Bloodshed) of Dev-C++ IDE and the Mingw compiler for creating a light, freeware environment for software development.

Conclusion

Lots of future work hopefully not including any bug fixes in my programs. The structure of my bot programs doesn't quite help anybody to set up a platform for further work, but it does give hints ;) Heres to a bot who can outthink a human given similar resources...

x1 AI (ugh!)

THE END

Penultimate

This will probably be the last update before the final presentation. D* was ditched because i had little time to understand it AND implement it. Used plain ol A* instead, first with recalculation on bumping into obstacle and then recalculation when obstacle comes into visibility range (still not sure if this is how it works ;) . Have a demo to give to Jotwani today, a report to rewrite tonight and print tomorrow morning, and last but not the least, make a presentation for the day after tomorrow.

Project D*

Demo uno on monday...have to implement and test D* before that. (?!?!)
jotwani sez take terrains of various roughness and show bot performance in the report. which means i gotta run a lot more tests now (which probably might fail).

Stentz's '94 paper on D* is what im using for reference. may god show mercy on me and my bot :S

Time to run for home base

Just finished 1st report soft copy. It has minimal experimental output. gotta change the crappy algo. will try and implement atleast A* if not D* although cant understand how situations goinna improve if i use the former.

Test Log

// TERRAIN PARAMETERS
// Seed Value is passed as an argument to srand(unsigned int)
567

// Roughness Constant for height displacement (.1 to .99)
.2

// Terrain Size (Integer: MAX 2049)
65

// Scales in metres of along the plane
25

// Scale in metres along height axis
1

// BOT PARAMETERS
// Bot Max no of steps (unsigned int)
// Bot run will be discontinued after this many iterations for stuck bots
2500

// Bot Starting X Pos (Should be in the range [0, TerrainSize - 1]
0

// Bot Starting Y Pos (Should be in the range [0, TerrainSize - 1]
0

// Bot Target X Pos (Should be in the range [0, TerrainSize - 1]
64

// Bot Target Y Pos (Should be in the range [0, TerrainSize - 1]
64

// Maximum slope that bot can traverse (absolute value)
// Floating pt angle in degrees (0, 90)
45

Testing with variable RANGE (1 - TerrainSize).

Distance covered seems to be directly proportional to RANGE. HELP!!!. Here's some data :(

RANGE (Cells) - Distance (m)

1 - 2836
2 - 3169
5 - 3298
10 - 2701
15 - 2792
19 - 2686
20 - 2586
21, 22 - 2565
23 - 2665
24, 25, 26 - 2645
27 - 2715
32 - 2707
41 - 2486
42 - 2465 <---------- WTF!!!
45 - 2468
50 - 2468
55 - 2468
MAX - 2468

Collecting my thoughts...

Didn't work the whole day yesterday. Couldn't figure out a simple way to figure out visibility of a cell. I looked at it from both points of view, but still couldn't think of an easy way out.

Then I thought, why not simple draw a straight line? The line-drawing algorithm occurred to me. I searched for Bresenham, and found this. Now I've written a function, which calculates visibility of a cell with respect to the another, completely ignoring cells which come in the way partially. Have to repeat this for all cells within max-range for bot to get good view of the countryside.

How am I representing bot perception of terrain? There are various kinds of terrain - explored/unexplored, passable/unpassable, visible/invisible etc. Anyway here follows the first few steps of the bot:

Basic Algo

* First thing to do would be calculate visibility matrix of surrounding area
* From that matrix, all visible cells, will be deemed explored
* A heuristic function will determine a target cell (explored) within this range (or within all the explored area...yet to be decided). This function should take into account the height of the cells too (since greater height will obviously help see more cells).
* Distance Transform will be performed taking all unexplored cells as impassable (taking worst case)
* Shortest path to target cell will be calculated. If found then bot will use the path to get to that cell, marking all cells on the way as visited. If path is not found then bot will try and move in the default direction of the target one cell at a time and re-run all the previous steps.

To be noted

* Cells once visited will need to have higher cost/heuristic value to discourage repeated visitations.
* Range one as mentioned before, is equivalent to FirstAgent and will be run as this.

Basically work is needed primarily on bot algo. Have to BBS Milda's program too to show that I haven't wasted my time completely with terrain generation. Till I figure something else out, or face steeper terrain...

Final Assignment

Still not having implemented the ranged bot on the terrain, I now have to implement the mofo with some line of sight. Yes, the word you are looking for is YIKES!!! And I only have myself to blame. Jotwani was happy with a satellite which told you everything there was to tell. I, like the stupid dork that I am, had to butt in and suggest this shit. Needless to say, it was an offer he couldn't refuse...just as long as "You should be enjoying what you are doing...that is all that matters". Sheesh! I now need a PC with network almost 24/7, and resources are becoming less accesible now. The only bright side is that I am to submit the report by the morning of 5th May instead of the 1st. Onto more technical issues...

A refresher

If bot's range is just 1 then it is equivalent to the FirstAgent and hence it will do normal brute force search, without a care for the shortest path (will work on this if I have the time. Which means I won't). If on the other hand, its range is more than it will find target cell within range of vision using heuristic from Amit's page, and find shortest path to it. Repeat this cycle till target is reached.

The job now

First and foremost is to find out what the bot can and cannot see. I'll try to be as least sophisticated as possible and hence I'll be taking cell-sized elevations/obstacles. Basically, I'll draw a line tangential to an obstacle. If the line covers more than half the area of the square then the bot's pretty much blind to it. It's not as easy as it sounds, not for me, not now (I hate thinking algorithms under deadlines).

For the bot, I'll keep another boolean visible variable to perform AND operation with. Default cost of unknown cell will be well....default i.e. unpassable. If I take elevation into account then I'd have more problems. More on bot movement algos later. First I gotta implement the mechanics of vision. And also think of a better algorithm for the vanilla ranged hopper so that it utilizes already explored terrain, and stops getting stuck.