NoAI Branch - An AI Framework

[corne]

But all the 'custom' written algorithms and optimizations is what makes an AI unique and fun to write. Don't let the API takes too much out of our hands

[fabca2]

But all the 'custom' written algorithms and optimizations is what makes an AI unique and fun to write. Don't let the API takes too much out of our hands

not everybody can make it own pathfinder, so having a basic API functions that make the job can be usefull too,
people that can make a pathfinder could avoid using it.

building an AI is not only making a pathfinder, for me making decision to deliver which cargo with which method (train/plane...) how many trucks, which power/speed/cost... is also very important and can makes difference between a good and a bad AI.

[Yexo]

Please post a detailed description of those pathfinding functions and/or some code and it might be implemented.

[fabca2]

Please post a detailed description of those pathfinding functions and/or some code and it might be implemented.

I don't know, maybe something like a first function (simulate) to know the cost between two tiles (and if it's possible or not)... and a function (build) to build it ?
it will for sure be a lot more complex than that... but with those simple high level API people who cannot build pathfinding can focus or other aspect of AI.
hard core dev can still continue to makes their own pathfinding of course...

just a suggestion.

[GeekToo]

I did build my own Astar based pathfinder with the API functions, but I agree with fabca2 that it would be nice for people that do not want to get into the pathfinder algorithms to have a basic pathfinder that can connect two tiles with roads. I also agree with Corne that part of the fun of writing an AI is in writing an algorithm for pathfinding. So maybe the API should be extended with a simple pathfinder, that can be extended (overloaded) by devs that do want to improve it. Or else a basic template for pathfinding could be published.

While writing my pathfinder, I encountered some problems, that may be solved by the API:
if you build a route in testmode, the map does not get changed. But then, when you build the route for real, building a route on a slope does create a foundation, that sometimes makes it impossible to connect to the next road part. This does make planning the route, before actually building it, hard.

So what I would like to have added to the API is a function that checks (also in test or transaction mode) whether a certain sequence of two road tiles can be built or not. For now, I solved the issue by checking in the planner that no curves are made on a slope ( which works rather well), but I would really like to be able to predict if a certain sequence can be build ( so no diference does exist between the planner, and the real builder ( apart from the map being changed by other players, that's a different problem))

[Caeddyn]

Like what fabca2 said the AI is more than just a basic pathfinder. If a pathfinder setup for railroad building comes across it's own railroad track, does it build a junction? What type of junction? What if it doesn't fit, should it look farther up the track? Should it terraform the ground or destroy houses? Is it possible that the piece track is already overloaded?

I think there should be a basic A* pathfinder in the API, since it would be not only faster, but so everyone doesn't have to reinvent the wheel all the time. However it seems that even if there were a basic one added, you may eventually end up having to make your own or make changes to the API version because it's not flexible enough to accommodate your needs. If it's decided that a pathfinder should not be added to the API, I think there should be more data structures like Binary Heaps and Hash Tables.

Eventually I’ll post the code for my C++ A* pathfinder. I haven’t yet because it's currently buggy and there might be some memory leaks. There’s also no comments and it probably doesn’t follow the OpenTTD coding standard.

[fabca2]

...you may eventually end up having to make your own or make changes to the API version ...

Yes thank you,
and you even don't need to "change the API version", if you are skilled enough to make your own pathfinder, you just don't use the one from the API.
adding API functions does not mean you must use them, it's just few new functions that you can use... or not.
So for people who don't want to use it, they can continue exactly as today, no need for modifying API or other stuff.

I whish I can find such API function that can build a very simple road from a point to another. not the smartest one, a very basic one... this will reduce complexity of AI I may build.

Of course, I speak about ROAD, train track is totally another topic (signal... etc...)

[Caeddyn]

I whish I can find such API function that can build a very simple road from a point to another. not the smartest one, a very basic one... this will reduce complexity of AI I may build.

Well there's the BuildRoad function in AIRoad. That will build a very simple road between two points.

A* is really not that hard to do. The only problem is getting it to run fast enough. However a more easier to implement pathfinder is the Distance Transform Algorithm. Im not sure if you can make it not build as many turns or up steep slopes, but it can find the shortest path between two points around obstacles like industries, lakes, etc. Here is some psuedo-code.

Anyway, I'm going to try to get my code finished today or tomorrow so I can post it. Then people could decide if they want to use it or work on their own.

[corne]

Maybe you guys are right, but it should be a very basic one or just the basic functions which are now slowing the AI down in squirrel (sorting, array searching, slope detection, etc).

Also I would like to request a function something like:
AIRoad.IsBuildable (starttile, endtile)

This would help me a lot

[Caeddyn]

You can use AITest and the do AIRoad.BuildRoad and it will tell you if it can build it or not without building the road.

[corne]

Ahh ok thanks, haven't looked at that testmode yet.

[Fingon]

The main things that should go in C++ code are the binary heap and the hashtable. Those can "easily" be extracted, and the lack of such functions is the main slowdown for squirrel. So if SQ could get some API functions for access to a binary heap and to a hashtable, that would be very cool! The benefit would be that the fun stuff of the A* algorithm would still be in SQ, so still fully tweakable by AI writers, while it would also be very fast.

There could be a fully C++ based A* for the people who are too lazy to play with their own pathfinder. The problem is that it can't be tweaked anymore - you could pass costs as a parameter of course, but if you want to add a special function (for example a penalty for building a road too close near a city), it would be impossible to add without recompiling the whole game.
But I am trying to get my squirrel based A* finished, and I will post it when it is done so others can also use it.

[fabca2]

but if you want to add a special function (for example a penalty for building a road too close near a city), it would be impossible to add without recompiling the whole game.

yes, but you could also use the poor-stupid-forlazy-APIpathfinder for some parts of the path and do what you want for other ones.
for example you want to joint 3 areas : A, B and C.
you compute in SQ the best "center" : "D"
you can invoke the API pathfinder for A-D and B-D, and D-C2.
C2 is a point near C. and you "manually" (in SQ) build road for C2-C because topography require it around C.
Example, in my API
I manage to use the APIpf when topography is easy only (for example).
And when it's not, I manage to work with SQ to make a lot of tunnels for example...

so in this (stupid) example, I would like to focus on computing D and C2 points, and finishing C2-C link, only.

[prissi]

Ok, I am not programming OpenTTD AI, but I worked long on the simutrans AI. But anyway my thoughs:

Most crucial is the placement of the stops/stations. Finding a connection is not crucial (also not for revenue). Especially, since OpenTTD has no road maintenance cost, i.e. once built they are free. Very critical for OpenTTD is imho the access and number of stops and the depot. This will govern throughput more strongly than one or two curves more. (The inbuilt "alpha AI" has imho a very good pathfinder. It even used bridges to avoid slopes and minimizes curves quit well. Certainly a good start for any AI.)

Breaking the path in subsections is mostly needed to cut down calculation time, imho. Usually such pathes gets more messy than the "globally optimized" A* path.

[Caeddyn]

I’ve looked at the code and I can see that the Alpha AI uses A* for it’s pathfinding. I’m not sure on how it decides on what towns to connect but it seems to make short routes, maybe 100 tiles max. And it lags my computer pretty good. My pathfinder can do 5-10 times the distance the Alpha AI can do with much less lag. Though it currently doesn’t know to build bridges or tunnels.

I do agree that a hierarchical approach to the pathfinding would yield faster results with not much loss in revenue. One approach could be to break the map into a grid, and on each wall of every cell find the “best” tile to connect to. Then instead of one large area you would calculate a bunch of small ones which you could probably store for later. Of course multiple AIs with the same plan would probably end up trying the same paths so you’d have to deal with that. But it could still result in a faster calculation.

[corne]

Sometimes when I try to run my AI with start_ai, OpenTTD keeps saying: 'The AI named "ai" is unknown or not suitable' and I have no idea how to solve it.
Anyone else having this problem?

*edit:
damn, I tried to "require()" a non-existing file problem solved

[Finaldeath]

Glad this is still being updated, I hope you fix the Win32 builds though, it took me a while to get it compiled due to an array of oddities on my system.

But once compiled it works successfully! yay!

Hope more functionality is added soon It'd be great to be able to get the AI difficulty and AI build speed parameters, and the various other options from the game options panel, along with a ton of other ones from the patches panel (such as vehicle limits, if tight turning is allowed , if buyouts are turned on, and what is enabled or disabled in the AI panel regarding vehicles).

Also; is there any plans to hook in some talking via. the existent multiplayer chat panel? I might not build the most efficient AI, but to have something fun to play against, I want to add a bit of personality to what it does. ("You cur, taking that subsidy! You'll rue the day you crossed Baggins Blockbuster Big Bags Box Cars!").

Squirrel is interesting. I'll have to see how it can work regarding loading data from external files - I don't want to hardcode all the parameters I build in if I can help it (although storing them in some structure or class would be an alternative, of course). Good work, I'll keep my eye on the development blog for more additions to the code and API.

Edit: Maths functions from squirrel would be useful too as i note, this was requested before, hehe.

[corne]

Could someone fix the win32 nightly build please

[glx]

You can find the win32 build in http://devs.openttd.org/~glx/noai

I'll build them until the compile farm is fixed.

[corne]

Thanks