Is This A Good Random Movement System?

Page: 1 2
ID:266045
 
Aug 23 2011, 12:58 am
Looking for people to critique this. Basically it only allows mobs to move a certain distance (Max_Move) from their initial starting position.

I feel like it could be better.

    New()
        while(src)
            if(New_Ent)
                New_x = x
                New_y = y
                New_Ent = 0
            sleep(rand(1,2))
            var/Dir = pick(1,2,3,4)
            if(Dir == 1)
                if((x + 1) <= (New_x + Max_Move))
                    Move(locate(x+1,y,z))
            if(Dir == 2)
                if((x - 1) >= (New_x - Max_Move))
                    Move(locate(x-1,y,z))
            if(Dir == 3)
                if((y + 1) <= (New_y + Max_Move))
                    Move(locate(x,y+1,z))
            if(Dir == 4)
                if((y - 1) >= (New_y - Max_Move))
                    Move(locate(x,y-1,z))
Aug 23 2011, 3:45 am (Edited on Aug 23 2011, 3:53 am)
You shouldn't have an infinite loop in New(). You want the New() proc to return at some point. (Instead use spawn() to start the loop after, allowing New to return.)

Also, here are a couple of ways I thought of doing it.
The second way is probably the nicer of the two.
    New()
        spawn()
            MoveLoop()
    proc
        MoveLoop()
            var/list/choices
            var/list/locs
            var/list/inrange = range(Max_Move, loc)
            while (src)
                sleep(rand(1, 2))
                locs = list(get_step(loc, NORTH), get_step(loc, SOUTH),
                                get_step(loc, EAST), get_step(loc, WEST))
                choices = new
                for (var/turf/T in locs)
                    if (T in inrange)
                        choices += T
                Move(pick(choices))
        //another way
        MoveLoop()
            var/minx = x - Max_Move
            var/maxx = x + Max_Move
            var/miny = y - Max_Move
            var/maxy = y + Max_Move
            var/list/choices
            while (src)
                sleep(rand(1, 2))
                choices = \
        block(locate(max(1, minx, x - 1), y, z), locate(min(world.maxx, maxx, x + 1), y, z)) - loc +\
        block(locate(x, max(1, miny, y - 1), z), locate(x, min(world.maxy, maxy, y + 1), z)) - loc
                Move(pick(choices))
Aug 23 2011, 4:27 am
What about the step_rand proc? That seems alot simpler.
Aug 23 2011, 4:33 am (Edited on Aug 23 2011, 8:45 am)
In response to Boxcar
Touché.
However, my methods ensure that the object will move every iteration of the loop. (In some cases, you want to restrict movement so that the object doesn't move too far from the starting position.)
In his original method, the object will sometimes not move at all if the randomly chosen choice would move it out of range. In my case, I made sure that it only chooses from movements that will keep it in range.

And step_rand() doesn't allow you to keep it in range.
[EDIT]
Plus, step_rand also allows for diagonal moves. I assumed he only wanted cardinal moves, because that's what his algorithm does.
Aug 23 2011, 6:50 am
Why not just use step_rand and get_dist to make sure you aren't going too far away?

Also, you don't want an endless loop in New(). make a proc then spawn it. See http://www.byond.com/developer/Deadron/EventLoop
Aug 23 2011, 12:39 pm
In response to Complex Robot
This is all still very doable. Override Move() to not allow diagonal movements, and use a get_dist() check with step_rand() as Jmurph said.
Aug 23 2011, 12:59 pm
In response to DivineTraveller
I feel like I'm the only one who notices a small issue with this.

If you disallow diagonal movements entirely, and the random generator just feels like giving only diagonal moves, then the object will just not move at all. (Okay, that's a little exaggerated, but surely there will be gaps of time where no movement occurs.)

And, with a simple get_dist check, I still don't understand how that prevents you from moving too far from the center.
I could see using get_dist on the place you're going to move to (get_step), but you should mention that, if that's what you mean. (And that still has the issue of hoping the PRNG shows you mercy by not trying to move you out of the range.)
Aug 23 2011, 1:02 pm
In response to Complex Robot
Well, sure, but a quick run-down of the reference shows me that step_rand returns 0 if it fails -- you can loop until you get a result.
You're right, get_dist() alone will not take care of the problem, but in a typical AI, you store the loc the monster was created on so it can reference it for pathfinding, or distance checking (such as this case), so although it's not included in the algorithm, it's perfectly feasible and easy to do.
Aug 23 2011, 1:13 pm
In response to DivineTraveller
DivineTraveller wrote:
you can loop until you get a result.

That's a very inefficient way to go about it. Having an unknown amount of iterations before it finishes is a very bad design decision, if you ask me. Especially when you can accomplish it with no iterations at all.
(And I checked the reference on that beforehand, thank you very much.)

I have no disagreement with anything else you've said.
Aug 23 2011, 1:18 pm
In response to Complex Robot
In most cases, yes, it is a very poor design choice. In this case, though, BYOND can calculate probably several hundred of those in a tick, there are eight directions, and only four are valid. You essentially have a 50/50 chance of it working, or not working -- the chance of it failing 500 (several hundred) in a row is 1/(2^500) -- in other words, it probably won't happen. Although this is not my first choice either, it certainly solves the issue at hand.

In addition, I never said you didn't check the reference, I said I had to check it, because I didn't know off-hand if it returned anything (though I was sure it did, I figured I should double check).
Aug 23 2011, 1:22 pm
In response to DivineTraveller
Okay. I understand what you mean.
I just tend to want every little thing to be as efficient as possible, because when they're all running at once, it could add up to poor performance.
Aug 23 2011, 1:23 pm
In response to Complex Robot
It sounds like you're trying to prematurely optimize everything. Just write it, make it work, and clean it up later. It's why we have a profiler.
Aug 23 2011, 1:29 pm
In response to DivineTraveller
I don't think it matters whether you optimize it now or later. And, since it's such an easy thing to optimize now, why wait? (And not every language has a built-in profiler. Sure, we're talking about DM, but the same concepts can apply to other uses.)
Aug 23 2011, 1:34 pm
In response to Complex Robot
--Because Someone Told Me To--

Premature optimization is bad.
Aug 23 2011, 1:37 pm
In response to Complex Robot
Aug 23 2011, 2:05 pm
In response to DivineTraveller
That is some really nice info. to know.

I don't think it applies to such a simple example, though. I could easily completely erase that code and re-write without a care. (Which is why I would erase it and put an optimized version there.) At least, in my opinion, it doesn't look any less readable.

Additionally, it might be more work to modify Move to get this to do what you want, when you might already have some functionality in Move that you don't want to change. (e.g. Some functionality that includes diagonal movement.)
I'm just pointing out that there's so many possibilities here, that you can't immediately say it's premature optimization. In fact, it's not even very optimized.
Aug 23 2011, 9:54 pm
In response to Complex Robot
I would have to say that I agreed with you Complex Robot, while that discussion did bring up some interesting and useful points. I can imagine that in a large project premature-optimization would be bad in that you're spending time optimizing something when you could be doing something else more worthwhile seeing as you don't know if the optimization is even worth it.

In this case however I'm looking to better my own skill and understanding. Not to mention that if I know how to make an efficient system compared to a non-efficient system is not logical to build an efficient system? That seems like it could be creating problems that I'll only have to fix later which is also bad ethics.

I think it's very situational and an issue one can't just simply throw a blanket answer over.

Thanks for all the responses too guys. I really wasn't expecting it.
Aug 23 2011, 10:24 pm
In response to Kyle_ZX
Fast is not free - fast code can often be extremely complex code, harder to use, harder to maintain, harder to understand.

Optimising code that isn't in the critical path can be a very bad habit if you make it harder to maintain and understand in the process. It's not just a matter of time spent optimising.

Of course, if your goal is learning about optimisation, that's one thing. If your goal is to make a useful program, that's another.
Aug 23 2011, 10:38 pm (Edited on Aug 23 2011, 10:46 pm)
In response to Complex Robot
I agree with you on this count - modifying Move() is definitely something to be careful of. In this case, modifying Move() feels way too global to my tastes.

Perhaps a better way of writing the limited rand-step proc:

mob/proc/limited_rand_step()
    var/list
        poss_directions = list(NORTH, EAST, SOUTH, WEST)
        poss_turfs = list()
        
    while(TRUE)
        poss_turfs.Cut()
        for (var/dir in poss_directions)
            var/turf/t = get_step(src, dir)
            if (t && get_dist(t, rand_step_centre) <= rand_step_limit && loc.Exit(src) && t.Enter(src))
                poss_turfs += t

        if (poss_turfs.len > 0) Move(pick(poss_turfs))
        sleep(rand_step_delay)


Usual caveats apply - poorly tested, may not even compile, etc. Assumes the existence of a 'rand_step_centre', 'rand_step_limit' and 'rand_step_delay' variable, performing obvious functions.

The poss_directions list seems like an obvious candidate for 
static
hood (that is, the declaration would be static/poss_directions), depending on how enthusiastically you trust undocumented, half-implemented features in DM. ;).

EDIT: Fixed minor mistakes with posted code.
Aug 23 2011, 11:25 pm
In response to Jp
My goal is to learn about optimization in order to help me make more informed decisions when making useful programs later.
Page: 1 2