[TI ASM/pseudo] General algorithms

[driesguldolf]

Some problems I couldn't solve and I don't really know where to start:

- Does anyone know a good filling algorithm to fill any shaped areas (like the ms paint fill tool)?
- How does pathfinding work (through a maze for example)?
- Ideas about how to implement a clever AI (not specific, rather what kind of stuff you need to take in consideration and implement those considerations)
- How are binary numbers converted to displayable decimal numbers (are there any other ways then dividing by 10 and take the rest or multiplying by 10 and take the upper part?)
- ... Any more problems are always welcome

Thanks

[benryves]

- Does anyone know a good filling algorithm to fill any shaped areas (like the ms paint fill tool)?

Lode's Flood Fill page might give you some ideas.

- How are binary numbers converted to displayable decimal numbers (are there any other ways then dividing by 10 and take the rest or multiplying by 10 and take the upper part?)

The easiest way I find is simply this (pseudo-code);

Code: Select all

bc = 0
do while a >= 100
    c = c + 1
    a = a - 100
loop
do while a >= 10
    b = b + 1
    a = a - 10
loop

Input: a; Output: cba = hundreds/tens/units. Add '0' to each before displaying, and it's probably a good idea to skip c if it's zero, and skip b if both it and c are zero.

[King Harold]

- How does pathfinding work (through a maze for example)?

http://www.policyalmanac.org/games/aStarTutorial.htm
there are more ways, like storing a pre-calculated path and moving semi-randomly over it.

- Ideas about how to implement a clever AI (not specific, rather what kind of stuff you need to take in consideration and implement those considerations)

that depends heavily on the kind of game it is, if it's a game at all. You can pretend to be the AI yourself and pay attention to the way you think, the kind of considerations you make etc. then try to write the AI so that it 'thinks' like you, it's easy to make a 'perfect' (unbeatable) AI that way, so add a chance factor somewhere. One of the the simplest AI's is that of Pong, it doesn't really do anything except making mistakes on purpose, common RTS games generally have a relatively simply AI as well, the hardest part of that is probably making it build a realistic city (if they have buildings) troops and resources are quite easy to manage.
Pathfinding could be considered a form of AI as well, it might or might not be, but atleast in RTS games it is a very important part of the game (you can't very well control every unit manually afterall)
Best do some research instead of reading my useless advises though

[driesguldolf]

Thank you VERY much for these VERY useful posts
I think it might be a good idea to make a sticky post containing information about this stuff

...and pay attention to the way you think...

I tried this with a card game, I tought it was a simple one, but man... It's amazing how the human brain handles such situations (this quickly results in an endless list of things to take in consideration)

[King Harold]

I tried this with a card game, I tought it was a simple one, but man... It's amazing how the human brain handles such situations (this quickly results in an endless list of things to take in consideration)

that's the problem with AI, and the reason that almost no robot even gets to the finish in the Robot Race..

[Jim e]

Blasted Asimov! His confoundable laws hinder robotic killing potential. Now all we can do is thin out the human race to prevent over population.

[CoBB]

Blasted Asimov! His confoundable laws hinder robotic killing potential. Now all we can do is thin out the human race to prevent over population.

Don’t worry, those laws are only applicable to robots with positronic brains. Our good old Turing machines are perfectly immune to them.

[cjgone]

A simple method for pathfinding is: (assuming that you can only move left,right,up and down)

check all four directions, find one thats not blocked, then take it (don't care which). On the matrix of the map, leave a "Trail" or some value to know you walked on it. Now check for another empty direction not blocked by a wall. If there is one take it, if not retrace your oldest path. Now after you go onto your old path, make a new "trail" on this square. For best solving, make the number of trails infinite (or something like 6 trails, etc). Make the pathfinders priortites that if you have not crossed the path, "0", it goes there, if there is no "0", go to the next trail "1", if there is no "1" , go for trail "2", so on... Walls, are no priority, since you can't go through them. Oh, and if 3 of 4 walls around a square are blocked, it's a dead end, and you can fill it in as a wall.

[driesguldolf]

I think I found a bug in TI flash debugger:
The carry flag is afected when an INC instr is executed (didn't test it with all posible inputs/parameters)

Try this program: (this figures the digits of a number (a) and returns a as units, b as tenths and c as hundreds)

Code: Select all

;header removed
   ld a, 23
   call decimal8
   add a, '0'
   ld (nr + 2), a
   ld a, b
   add a, '0'
   ld (nr + 1), a
   ld a, c
   add a, '0'
   ld (nr), a
   ld hl, nr
   B_CALL(_puts)
   ret
nr: .db 0,0,0,0
decimal8:
   ld bc, -1
_hundreds:
   sub 100
   inc c ; This one cleared the carry flag
   jr nc, _hundreds
   add a, 100
_tenths:
   sub 10
   inc b
   jr nc, _tenths
   add a, 10
   ret
.end

You'll see that in flash debugger it results in 279 and on a real calculator 023 is displayed! (Altough I this is just one of the many bugs in flash debugger... it's the most anoying tough )

Crap, I actually only used flash debugger because I can't get a rom image... (others have no usb support/my computer does't have a serial link port...)

[tr1p1ea]

You can use Rom8x to aid in the building of a rom file.

http://www.ticalc.org/archives/files/fi ... 37341.html

[Jim e]

Those CLC files included with flash debugger are rom files. I believe they store it the actual rom at the beginning of the file and the rest of the extra afterwards. So any good emulator should read it without to much trouble. If there is trouble you only need to truncate the file to 512k(assuming the 83+ is what you want to emulate).


Flash debugger is a decent debugger, but a very poor emulator.

[Halifax]

Anybody know how to build pathfinding AI for 3D games??

[King Harold]

The same way as on 2D, just extend it to go into the 3rd dimension aswell, forexample: instead of checking all 8 squares around you, check all 26 cubes around you, all coordinates will - ofcourse - have to contain a 3rd element.
The amount of memory really explodes when adding dimensions, you won't want to try a 4th or 5th in a real-time game (it's not like you'll need them anyway though).
Many 3D games use pre-calculated paths which are stored with the maps, and do not do any pathfinding at all (units sometimes get stuck in those games), and there are a lot of 3D games in which you can only walk on the ground anyway - then pathfinding is just 2D.

[driesguldolf]

check the pathfinding link a bit higher, he says something about nodes, nodes are used when you don't have a nice width x height map (like in 2d) so the nodes fullfill the purpose of the "tiles" (but you have to tell him wath nodes are linked together, this is obvious with tilemaps)
for the rest, this is axactly the same as 2d pathfinding
(If you have hl2 ep1 then you can get a visual representation, with the "commentary" on play the hospital level, near the turrets a comment will explain and visualize the nodes)

[King Harold]

Linearly interpolating Sine's (the results are not perfect, but match TI's sines if the resolution is high enough):

R is the resolution (number of elements in S[]), S[] is the list of sines. X is the number you take the sine of, in radians. Note that degrees would be faster.

double sine;
if (X%2pi < pi)
{
sine = lerp(S[R(X%pi)],S[R(X%pi)+1],((R(X%2pi))%1));
}
else
{
sine = -lerp(S[R(X%pi)],S[R(X%pi)+1],((R(X%2pi))%1));
}

if you don't know what lerp does:
lerp(a,b,c) = c(b-a)+a

I tested it with a resolution of 64, and that worked well enough, 32 would probably work well enough for most purposes, powers of 2 are faster to perform a MOD ( % ) on, so I would recommend using them instead of odd numbers: mod pow(2,X) can be done with 'AND (pow(2,X)-1)', instead of a division.