NoAI Branch - An AI Framework

[Rubidium]

P.S. Since publishing local_pathfinder, I have not received a single reply about. I'm very interesting: is it usable?

It looks promising on the looks I had at it so far, but I have not had enough time to properly test and review it (and won't have that time the next two months), so it's basically waiting till I (or another developer) has the time to continue with the NoAI branch; getting 0.6.0 out is currently a higher priority task (for me) than implementing/developing new features. I have a dedicated checkout with this patch applied so forgetting about it is quite hard.

[SjaakOnderkaak]

I think I located the bug. The reason is due to calling " this->RemoveItem(*iter); " in the inner loop of the buckets, i.e. the AIItemList of the bucket values. When RemoveItem is called and the bucket is empty, the bucket will be erased, invalidating the next_iter and iter iterators. Hence VC libs will generate an assertion error at the tail of the for loop when " iter = next_iter " is executed.

I modified RemoveBottom and RemoveTop similarly as shown below.
Now Zuu's WrightAI works and they are building planes everywhere!

[..]

Well I ran into this problem as well. Strangely the automatic builds at http://nightly.openttd.org/noai/scoreboard.php don't seem to be experiencing this problem while executing. I determined the problem to be in the second for loop:

Code: Select all

            for (AIItemList::reverse_iterator next_iter, iter = items->rbegin(); iter != items->rend(); iter = next_iter) {
               if (--count < 0) return;
               next_iter = iter; next_iter++;
               this->RemoveItem(*iter);
               num_items--;
               if (num_items <= 0) break;
            }

What is actually happening is iter being destroyed during the call to this->RemoveItem(*iter) as you pointer out correctly. Now it is not the 'iter = next_iter statment' in the loop that's causing the problem, the problem seems to be in the statement 'iter != this->buckets.rend()' in the for loop. Since iter was destroyed in the last executing of the loop becoming some random garbage value, iter will never match this->buckets.rend(), causing the the loop to be executed after the list became empty and thus making xtree throw errors because you are trying to remove no existing items.

So here's the fixed version of the loop (of course xargonax's version isn't wrong, but this one should execute just as fast as the original routine. With list's being used quite often, I think speed is a must in this code):

Code: Select all

				for (AIItemList::iterator next_iter, iter = items->begin(); ; iter = next_iter) {
					if (--count < 0) return;
					next_iter = iter; next_iter++;

					// Check if the next item is the end of the list, if so delete current item and break out of the loop.
					// This check was previously done in the for loop, causing the check to be done AFTER
					// the item was deleted and thus the pointer value was destroyed, causing is never to
					// match 'items->end()' and making xtree throw and exception about this
					if(next_iter == items->end()) {
						this->RemoveItem(*iter);
						break;
					} else {
						this->RemoveItem(*iter);
					}
				}

By the way, I am not some kind of c++ expert, but by closely examining the execution process you may stumble upon some strange constructs from time to time.


About the whole path finding stuff; I've been looking into this as well for the last few day's. The last 'experiment alpha ai' was quite able to construct sensible routes for trucks and busses. While I haven't looked into the complete details, I suspect the following path finding algorithm is used: http://www.policyalmanac.org/games/aStarTutorial.htm This tutorial provides some incredibly nice information about the whole path finding fuzz, including how to deal with longer distances (larger grids) and path smoothing (train alert!!).

[Morloth]

Hi, I'm currently working on an AI implementation but I've stumbled upon a problem with the AIRoad.BuildRoad() function provided by NoAI. I've got a working pathfinder for roads written in Squirrel, but when I try to build the actual roads this is what happens:



So any road from North -> West and West -> North simply won't connect, does anyone have similar problems? I've posted the code I use to construct the roads below, roadList is an array filled with tile identifiers for all tiles the road will be constructed on. Road being an instance of AIRoad. I've checked the tile identifiers and I don't see any problem there. The calls are similar to:

AIRoad.BuildRoad(A, B);
AIRoad.BuildRoad(B, C);
AIRoad.BuildRoad(C, D);
etc...

If someone could provide me some insight into this problem I'd be very grateful.
Thanks in advance!
- Bram

Code: Select all

/**
 * Create the fastest road from start to end, without altering
 * the landscape. We use the A* pathfinding algorithm. 
 *
 * The allowenceSavings is used to specify how much longer a road 
 * may be if it saves on the costs of building roads. The value 
 * must be between [0..1], 0 meaning NO detour may be made to 
 * lower the costs, 1 means that any means must be exploited to 
 * lower the cost as much as possible (existing roads are 
 * considered to be free).
 */
function RoadPathFinding::CreateRoad(start, end, allowence)
{
	local roadList = this.FindFastestRoad(start, end, allowence);
	if(roadList == null)
		return false;

	// Build the entire tile list! :)
	local i = roadList.Begin();
	local j = null;

	// We want to build entire segments at once. So if our road goes North
	// 5 times we want to build it with one command, instead of calling
	// BuildRoad 5 times (saves time! :)). So we keep track of the direction.
	local direction = null;
	local lastChecked = null;

	/**
	 * We use an iterating process. We monitor if each sequential tile
	 * heads in the same direction as the previous tile, if not we 
	 * construct the road found so far and continue the process in 
	 * the new direction.
	 */
	if(roadList.HasNext())
	{
		// Check the initial direction
		local j = roadList.Next();		
		local currentDirection = j - i;

		// Skip list till we find a tile with an other direction
		while(roadList.HasNext())
		{
			lastChecked = j;
			j = roadList.Next();

			// If the road changes direction, create that part of the road
			// and change the direction we're heading
			if(j != lastChecked + currentDirection)
			{
				road.BuildRoad(i, lastChecked);

				// Update new direction information for the next
				// iteration
				currentDirection = j - lastChecked;
				i = lastChecked;
			}
		}
	}
	
	// Build the last part (if any)!
	if(i && j)
		road.BuildRoad(i, j);
	
	return true;			
}

[Morloth]

D0h, foolish me. I used a AITileList instead of a normal AI to store the tiles... It works as it should now

[Zephyris]

Nice work with the roads, looks like a good pathfinder! Rail building isn't supported yet is it? It will be so good to see that in action...

[Morloth]

Nice work with the roads, looks like a good pathfinder! Rail building isn't supported yet is it? It will be so good to see that in action...

Thanks, but it's not that impressive (yet! ). Railroads are not supported due to the constraints of this competition I'm working for -> http://www.tt-forums.net/viewtopic.php?f=29&t=36059. Although I do plan to make it into a full fledged one once the competition is over. Till that time only roads and vehicles will be supported.

[Morloth]

Hi everyone!

I've been working on my AI for the last couple of days, but found I had to add some functions to the NoAI API, also most of the methods in the API should be static so I made them so. The new patch is located at: http://bugs.openttd.org/task/1783, I hope someone can look at this!

For those who are wondering about my AI implementation (dubbed RoadBuster!), take a look at this screenshot: http://aycu30.webshots.com/image/44109/ ... 876_rs.jpg

It's far from perfect:
- It has problems doing pathfinding on rough mountainous terrain
- It only builds once and does nothing else once this is done
- My calculations about travel times, how much a vehicle can transport / m, etc. are not right on just yet (it's comming there though )
- Bridges aren't recognized yet
- And some other stuff .

Please look at my patch and I'll keep you posted on my progress!
- Bram

[RMJ]

Hi everyone!

I've been working on my AI for the last couple of days, but found I had to add some functions to the NoAI API, also most of the methods in the API should be static so I made them so. The new patch is located at: http://bugs.openttd.org/task/1783, I hope someone can look at this!

For those who are wondering about my AI implementation (dubbed RoadBuster!), take a look at this screenshot: http://aycu30.webshots.com/image/44109/ ... 876_rs.jpg

It's far from perfect:
- It has problems doing pathfinding on rough mountainous terrain
- It only builds once and does nothing else once this is done
- My calculations about travel times, how much a vehicle can transport / m, etc. are not right on just yet (it's comming there though )
- Bridges aren't recognized yet
- And some other stuff .

Please look at my patch and I'll keep you posted on my progress!
- Bram

Looks very nice... i know its cool to play with other people. but sometimes one just might not have the time or be a place where there is internet. i for one, would like to someday see an A.I thats builds like this with road and trains wow. would add A LOT to openttd keep up the good work.

[RIVDSL]

I have been experimenting with the API recently and have to say that I have been waiting for something like this for years. Too bad there is no support for trains yet, but road vehicles are difficult enough to start with anyway.
The wiki indicates that output messages should be printed in the internal openttd console, however that seems not to be the case. In the win32 version the system console does also not print any messages, which makes development really hard (the Linux version does, fortunately).
When the difficulty settings are set for the AI to start immediately it can still take a few months for the AI to start. When I want to test something quickly this can be quite annoying, I would like to see the option for the AI to really start immediately or a console command which starts a new AI.
Unfortunately I have lots of other things to do right now, but I am certainly planning on using this API to create a challenging AI someday. Keep up the good work!

[glx]

Use -d switch to open the debug console on windows.

[Morloth]

When the difficulty settings are set for the AI to start immediately it can still take a few months for the AI to start. When I want to test something quickly this can be quite annoying, I would like to see the option for the AI to really start immediately or a console command which starts a new AI.

A patch has been created by a colleague of mine, it gives you control over which AIs will join the game and lets them start immediately. It hasn't been reviewed yet, but if the patch is ready for production I'll post it here.

Good luck with you AI!

[yorick]

When the difficulty settings are set for the AI to start immediately it can still take a few months for the AI to start. When I want to test something quickly this can be quite annoying, I would like to see the option for the AI to really start immediately or a console command which starts a new AI.

You can use the console command "start_ai <ai>" to start an AI

[GeekToo]

I've updated my AI to latest svn, and managed to make it profitable with only buses. But I don't think it does perform very well, though I do not have any figures to compare it against. So, here's the question: how much profit should a bus make, and how much profit does the default ( not noAI ) AI make using only buses?
My AI does earn 22500 in the first year, but I think that's not enough, does anyone have numbers to compare it with?

[Zuu]

It depends much on the map etc. But if someone composes a map then comparing can be done. If the map does not contain too many industries, lakes or other multi-tile obstacles my Clueless AI written back at r9??? can preform quite well. (quite well = make profit )

Out of interest, do you do inter city traffic? And if so, what principles does your road builder path finder uses?

Myself I used a quite dumb road builder that alternate between going in X and Y direction (continuing in either direction until and obstacle is reached or goal X or Y is reached. Plus some hacks to handle minor obstacles.


Edit:
But you wanted figures, so here you get figures.

On attached scenario with one replication my AI had 19 000 as income first year using r9593. (console command to start AIs did not exist in r9593, so some delay in the beginning before the AI started)

[Caeddyn]

I've updated my AI to latest svn, and managed to make it profitable with only buses. But I don't think it does perform very well, though I do not have any figures to compare it against. So, here's the question: how much profit should a bus make, and how much profit does the default ( not noAI ) AI make using only buses?
My AI does earn 22500 in the first year, but I think that's not enough, does anyone have numbers to compare it with?

I was interested in figuring out the same information myself, so I ran a couple of tests. I knew about the "Default" AI and how bad it is. But I saw that there's also an "Alpha" AI under the patches menu.

For the year 1951 the Default AI lost -$25,566. It had 8 busses and it made an average of only $1421 per bus. The routes it made were very long, and had some odd turns. Its major flaws were that it didn't build enough busses, and it made poor routes in general.

For the year 1951 the Alpha AI made a profit of $37,874. It had 7 busses and it made an average of $7708 per bus. The routes it made were much shorter than the Default AI. It seemed to have a decent understanding on which towns to connect, however it didn't build enough busses.

Now for the past few days I have been working on my own AI named RhodeBot. It currently only works on perfectly flat terrain, and it only connects one coal mine with a power plant.

For the year 1951 the RhodeBot made a profit of $164,146. It had 37 trucks, and it made an average of $5536 per truck.

[Fingon]

The "Default AI" is so bad at busses because it takes every subsidy no matter how bad that subsidy might be. The profit of busses in the first year is not a very good measure anyway, because the passengers still have to realize that there suddenly is a busstation in their town now. Second / third year profit is better, but still it's a problem if your AI keeps adding new lines constantly (which it should).

I'm working on my own AI too, MotorcadeAI, so far just trucks but I wrote a good A* pathfinder. It avoids obstacles, and tries to re-use existing roads where it makes sense, so the eventual map layout is pretty nice. But despite this it is still quite hard to make a decent profit. Every truck in my AI makes an average profit of £1000 to £2000 a year. Tested on "medium" difficulty setting, so with breakdowns and hills and all the hard/realistic stuff.

It would be nice to be able to compare our different AI's in a fair way. As Zuu says, the performance depends on a lot of things, so we should set up a number of different scenarios/savegames, about 3 to 5 would be ok i think. Different starting years, different difficulty settings, etc, going from very easy to very hard for an AI. And with only trucks and busses allowed. As for map sizes I would choose both 256 x 256 or 512 x 512. Smaller might be too hard, and bigger might be pointless.

Zuu : i do not have r9??, and the latest r???? can not open your scenario...

[Zephyris]

Wow, that looks really nice! I would be happy if those were my on truck routes

[GeekToo]

Thanks for the info Seems I still have got something to do, esp in comparision with the coal trucks.

I did start the game with the following seed:
-g -G "579140164"

512x512 map, flat, low towns, start 1950, temperate

Zuu, for your info, I only use intertown buses, but I plan on adding intratown buses to feed them, using drive through stations.
The pathfinder is still very basic, only straight x and y connections with one corner max, but I plan on looking into A star (though someone already did that).

[Zuu]

Zuu : i do not have r9??, and the latest r???? can not open your scenario...

As said on IRC I've brought Clueless up to current revision, well to the extent that it runs but still would benefit from the many new API functions added since r9593. I tried to use the attached scenario on current revision but failed too. So yea, quite useless now.

But I second the idea of creating a set of reference scenarios.

Some things to consider is patch settings. For example build on slope complicates quite a bit for the AI, but guess that have to be some kind of requirement as most players play with it on. Now that we have slope detection API functions an AI can detect the slopes and act as if it was of, with the only addition that it has to care about half-tile roads on slopes.

[Fingon]

Ok I made an easy scenario. Pretty flat and smooth terrain, nice towns, nice industries. It's attached, but for the record, the settings are:
Easy difficulty, with following changes : 4 competitors, immediate start
Default patches, with changes : 5,000 vehicles maximum (instead of the normal 500 so an AI has ability to grow), 0 trains, 0 aircraft, 0 ship.
No NewGRF
Land generator : 512 x 512, seed = 123456789, Terrain type Flat, Sealevel Very Low, Smoothness Smooth. Normal towns (many random towns of medium size), normal industries (Many random industries), start date = 1950.
Let me know if there are problems / suggestions. And if there are no problems, post some results!

Also, I find that building on slopes actually makes things easier, as the AI can build very long straight lines without problems if slopebuilding is possible. Without it a lot of twists and turns are needed, especially in hilly terrain.
Anyway if slopes are a problem, or this scenario is too hard because of the towns/industries interfering with the pathfinding, then you should make a totally flat scenario yourself and post it too.