An AI challenge

[timfoden]

Oops! That'll teach me to 'borrow' code! Can you tidy it up for me Tim?

OK, I've made the changes.  As I said, they were fairly minor bugs really.  The code is in http://www.7sun.com/temp/fow/FOW.java -- EDIT: this is the FOW from the previous release... I'll just get the new one now and see if its the same.  UPDATE: OK, I merged my changes into the new version of FOW.java now, and uploaded it to the same address.


While I was looking at making these changes, I found code that I believe can be made a lot more efficient.

For example, the lineOfSight routine calls canMoveTo(x,y) for each point tested along the line, but canMoveTo(x,y) tests for hitting a pillar each time.  This means that it's doing a pillar hit test for each pixel in the map along the line being tested.  I think lineOfSight would be faster if it found the closest pillar once, and then used this info to limit its search in the map.

Would you like me to have a go at fixing this too?

Cheers, Tim.

[SimonH]

OK, I've made the changes.

Thanks!

lineOfSight routine calls canMoveTo(x,y) for each point tested along the line.
Would you like me to have a go at fixing this too?

Would you mind? I can't believe I missed that!

[Jackal von ÖRF]

Optimizing the canMoveTo and canSeeBetween methods would improve the performance of my bot, because those are its hotspots. But when I switch to using castRay, it should anyways use much less CPU. Casting some 100 rays each step should be faster than calling canMoveTo 10000-50000 times each step.

Games published by our own members! Check 'em out!

[SimonH]

Optimizing the canMoveTo and canSeeBetween methods would improve the performance of my bot

That's true, but it'll also improve the performance of everyone elses...
The advantage of optimising the ray casting is that it means tests will run faster. castRay() will always have a cost so the fewer (and shorter) rays a bot casts, the better!

[timfoden]

OK, there's a new version of FOW.java available.  It has some of the changes to make the lineOfSight and canSeeBetween routines faster.  It seems to make my bot about 2 to 3 times quicker.  I've got some more changes planned though, so please bear with me.

Cheers, Tim.

[Jackal von ÖRF]

Good changes, Tim. My bot's CPU usage has dropped by 50-75%. Now 75% of my CPU time goes into checking all cells on the map with the forbidden canMoveTo method. I should be able to drop the CPU usage by at least 50% by changing the way that I look for obstacles, unless I manage to make a very CPU intensive way of doing it. I have some ideas on how to recognize those pillars even if they would not be moving... let's see how much CPU it will require.

But first I'll need to take a pause and concentrate on work. I'll come back in a couple of weeks.

[timfoden]

Here's another iteration of FOW.java with some more speed improvements.

In my timings (4 runs, square maze) the previous version has an average of 0.524 ms/turn.
This new version has an average of 0.353 ms/turn for the same maze.

This is not such a large improvement as the previous iteration, but I think it's worthwhile non-the-less.  I don't think I'll be looking at any more speed improvements at this time. 

Cheers, Tim.

---
A quick note about timings... I had to change to nanoTime() to get the accuracy shown here.  It would seem like a good idea to do this for all bots, and further, to take the timing code out of the bots completely.

[SimonH]

Thanks Tim! That's given a it huge performance boost. (what a klutz I am!)

BTW I originally used nanoTime() but found it totally inaccurate (2 identical bot's timings differing by a factor of 10).
Is there some trick to using nanoTime?

[timfoden]

I've never had any problems with using nanoTime() instead of currentTimeMillis().  I've only tried it on Windows machines, but other posts that I've read that mention it are from people running Linux machines.  I can't remember anything about it's MacOS implementation.

It is necessary to check that the time hasn't gone backwards (which it does when the counter wraps... the documentation is a bit misleading there -- it wraps quicker than the documentation implies).  But your code already does this for the currentTimeMillis() version anyway.  The only other point is that of course the value returned is in nanoseconds not milliseconds.

Oh, one other thing... there seems to be a minor problem with it on multi-core AMD processors.  nanoTime is based off the cpu's high resolution timer, and on the multi-core AMD processor each core has it own timer, and it seems that they can get a little out of sync.  But apparently just rejecting times that go backwards tends to fix the problem fairly well.

UPDATE:

see Game Timer

As an aside, I wouldn't suggest switching to System.nanotime.  That particularly timer doesn't work reliably on processors with energy saving capabilities (which is common, especially on laptops) and older dual core AMD processors.

-- doesn't sound good does it? 

also see NanoTime for Dual Core AMD systems
-- this one has some sample code for dealing with the problem.

Cheers, Tim.

[SimonH]

Few minor changes. (source here).

Collision detection is now accurate (per-pixel), which has broken my bots (not Tim's or Jackal's though)

I've added a new (nightmare) map which breaks all the bots except NoAI (evil chuckle!) 

I wouldn't suggest switching to System.nanotime

Doesn't sound so good...