Programming Megathread

[ZSNO]

"deque" is something new to me. I only just learned about vectors when I did that tutorial last night. I was going through the RIT course notes.

It's nice to learn about the different containers and their efficiency.
Deque (pronounced deck) can efficiently add and remove elements from the front and back of the element array because of the weird implementation.
Adding an element to the front of a vector is not good.

[Ad Bot]

[Pecon]

can efficiently add and remove elements from the front and back of the element array because of the weird implementation.

I believe that this behavior is most commonly found in linked-list structures.

[Ono-Sendai]

I believe that this behavior is most commonly found in linked-list structures.

deques are much more cache friendly than linked lists even if you have a custom allocator for the linked list. it depends on the use case. code that needs to be performant generally shouldnt use linked lists. obviously that doesnt mean you SHOULDN'T use something like std::list anywhere but its just something to keep in mind.

[ZSNO]

I believe that this behavior is most commonly found in linked-list structures.

Linked-lists are the best at removing elements in the middle of the list (as long as you have an iterator already there!), since all it needs to do it redefine the pointers to the next element.
A deque's implementation is a vector of vectors, where the first vector is reversed, so it lends itself to being able to remove elements at both ends.

[McJob]

So, over the past two days I began implementing an EXTREMELY simple AI system. Here's what I've got (from the Game Dev megathread):

VacBot, the cute little yellow cube, is based on this task-based system I've been working on. Aside from the fact he's extremely simple (he can only move forward and left), he also doesn't yet implement all the functionality I want for my AI system, but right now the way he works:

1) On the first update, he gives himself a task to complete ("Move Forward", assigning tasks will later be completed by another system).
2) Every task returns a bool on if it's complete or not (for example, Move Forward will only be complete if he's reached the end in this instance), and Task Manager uses the return value to say if we need to re-add the task to the task list so it can be processed again.
3) Every time we do a Move Forward task, a simple raycast is done in front to determine if there's an obstacle. If one is detected, the Move Forward task returns false and instead manually adds the "Clear Obstruction" task to the list.
4) Clear Obstruction performs a move operation to the left and then does three raycasts to determine we're not touching anything. I'm using only three because this example means he's only ever going to be going forward.
5) When Clear Obstruction finally stops repeating, the system will auto-assign Move Forward to the task list, and the cycle continues until it reaches the goal.

This thing is AI because it's dynamic. I can add as many obstacles as I want at any point, and he'll (almost) correctly handle that. There's a LOT of work to go from here, but I'm super happy I got the basic roots of task-based AI down (using delegates, since Unity/C# don't support function pointers).

EDIT: Should be noted; the task-list is a stack. The idea is that higher priority tasks are added at the top and completed before lower-priority tasks. In the end I'll likely change this, but the behaviour is working well for now. I'm also using single-parameter delegates for my tasks, although I will likely change this to be zero-parameter, instead using class variables where possible. I'm still working out the semantics as I go.

[Waru]

so in gml is there a way to cascade arrays?

like

Code: [Select]

array[0] = 5
array[1] = 6
array[2] = 7
array[3] = 8
array[4] = 9
array[5] = 10
array[6] = 11

and you do a command so all the arrays are down one?

like

Code: [Select]

array[0] = x (entered later)
array[1] = 5
array[2] = 6
array[3] = 7
array[4] = 8
array[5] = 9
array[6] = 10
array[7] = 11 (or deleted to keep only 7)

i know i can do it with a long string of array[1] = array[0] going backwards from whatever max I want, but just wondering if there's a better way.

[Foxscotch]

I'm not sure what you're trying to do. you want to move every item in an array down a few indices? what happens to the items that would be below index 0?
I don't understand the second example at all. what do you mean "entered later" and "deleted to keep only 7"?

[Waru]

I'm not sure what you're trying to do. you want to move every item in an array down a few indices? what happens to the items that would be below index 0?
I don't understand the second example at all. what do you mean "entered later" and "deleted to keep only 7"?

i want to move everything up?

I have 7 indexes at the start, i was wondering if there was a way to move all indexes from x to x + 1, and then fill in the index of 0 with something, the last part about "deleted to keep only 7" meant having array[7] cleared so the number of indexes is always 7. (Which can be solved by just not writing to [7]

i know it's completely possible to do something like

Code: [Select]

array[0] = 5
array[1] = 6
array[2] = 7
array[3] = 8
array[4] = 9
array[5] = 10
array[6] = 11

then

Code: [Select]

array[0] = 4
array[1] = array[0]
array[2] = array[1]
array[3] = array[2]
array[4] = array[3]
array[5] = array[4]
array[6] = array[5]

i was just wondering if there was a better way to do it

[Kingdaro]

Something like this?

first = array[0] + 1;
for (i = 0; i < len(array); i++) {
  array[i] = first + i;
}

I'm not sure what it'd be exactly in GML, but it's what you're most likely looking to do. That, or a push/pop function for arrays, if GML has it.

[Foxscotch]

oh, the first list was the starting list, and the second was the goal
lol, that explains a lot. I was thinking you were saying like, array[0] = array[5] or something
(the confusion came from you using "=" instead of "==")

anyway idk GML, but this would work in javascript

function cascade(oldArray, x) {
    var array = [];
    for (var i = 0; i < oldArray.length; i++) {
        array[i + x] = oldArray[i];
    }
    return array;
}

the x argument is for the number of places you want to move everything up. to get what you want, you'd just use 1

< x = [1, 2, 3]
< y = ['hey', 'hi', 'hello']
< z = [3, 2, 1]

< cascade(x, 1)
> [undefined, 1, 2, 3]
< cascade(y, 2)
> [undefined, undefined, "hey", "hi", "hello"]
< cascade(z, 3)
> [undefined, undefined, undefined, 3, 2, 1]

[Waru]

i got it like this

[Foxscotch]

are you only doing it once?

[McJob]

Code: [Select]

/********************** AI SYSTEM - PARENT CLASS - v0.01 **********************/
 
//Made By: Ben "McJobless" Steenson
//Date: 2016-03-15T12:50:00+11:00
 
//This parent class for the AI System holds the basic functionality that all AI systems will utilise.
//Most of the things inside this parent class should be overriden (including the Data struct using the "new" keyword to hide the default).
//Anything that is core to this system and cannot be overriden is marked as private; everything else is protected (as only derived classes should need access).
 
//AI FRAME UPDATE PHASES:
//1) Initialisation: Methods are assigned to delegates, default behaviour lists are filled and the default state of the AI unit is all filled in the Awake() method.
//2) StateController() is run, and any state-specific behaviour (such as assigning timers) can be run.
//3) At any pointer, using the CurrentState accessor will run StateSwitcher(), which handles transitions between states.
//4) Once States are dealt with, TaskController() runs and will attempt to fill an empty taskStack or run the top task in the stack and then read it if required by the task conditions.
 
//Changes to make:
//0) Need a way to disable AI thinking; would be great if AI outside of rendering distance are automatically disabled.
//1) AI system has no clean way to handle task INTERRUPTIONS (especially for things like gravity-defying rotations).
//2) Need to verify data accessibility (such as adding accessors for the data containers) and also make certain parts easier to extend.
//3) Integrate the Seeker task-generation system in whatever form that may come.
//4) Node-Based Pathfinding.
//5) Make a simple demo of an AI-driven unit following an object which moves randomly around the world.
 
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
 
public class ParentAI : MonoBehaviour
{
    /* VARIABLE DEFINITIONS */
 
    //Data-Type Definitions
    protected enum AIStates { IDLE, MOVEMENT };                                                             //All states that an AI can exist in; I'd like to make this extendible so no edits need to be made to this file by a user.
    protected delegate bool Task();                                                                         //An AI-specific function that can return true if it needs to be replaced on the stack.
    protected struct AIData                                                                                 //A struct which holds AI-specific data (such as health and speed). Will likely be replaced with another form down the track.
    {                                                                                                       //The struct is designed to be overriden/hidden with the "new" keyword in derived classes.
        public float sightDistance;
        public AIData(float sD) { sightDistance = sD; }
    }
 
    //Data Containers - THESE SHOULD HAVE ACCESSORS TO PREVENT UNAUTHORISED ACCESS!!!
    protected Dictionary<AIStates, List<Task>> defaultTasks = new Dictionary<AIStates, List<Task>>();        //Defines which tasks should be returned on the stack if it's empty based on current state; allows multiple tasks to be imported at one time.
    protected Stack<Task> taskStack = new Stack<Task>();                                                    //This stack holds the tasks that the AI will attempt to complete in order from top priority (last in, first out) to lowest.
 
    //Variables: State Accessor
    private AIStates currentState = AIStates.IDLE;                                                          //Holds the current state of the AI, which can change certain behaviours and conditions.
    protected AIStates CurrentState                                                                         //Accessor is used to clear the task list (interrupts should go here) and run the transition manager (StateSwitcher()) before directly changing the state.
    {
        get { return currentState; }
        set
        {
            taskStack.Clear();
            StateSwitcher(value);
            currentState = value;
        }
    }
 
    /* METHOD DECLARATIONS */
 
    //Technically these are method definitions, but they're empty in this parent class and must be filled out in derived classes.
    protected virtual void StateController() { }
    protected virtual void StateSwitcher(AIStates toState) { }    
 
    /* METHOD DEFINITIONS */
 
    //Run once per frame; user should call this base version before/after their update code to run the task controller.
    protected virtual void Update()
    {
        StateController();
        TaskController();
    }
 
    //Handles all Task-related processing; this should never need to be modified and so it private and only handled in this base class.
    private void TaskController()
    {
        //Temporarily save the current task in case it needs to be repeated later.
        Task tempTask = null;
        if (taskStack.Count > 0) tempTask = taskStack.Peek();
 
        //If we haven't completed any relevant goals (and therefore aren't just sitting idle), run the task checks.
        if (taskStack.Count == 0) { foreach (Task item in defaultTasks[currentState]) if (item != null) taskStack.Push(item); }     //If the task stack is empty, fill the stack with the default tasks based on the current state of the AI unit (ignore any null tasks).
        else if (taskStack.Pop()()) taskStack.Push(tempTask);                                                                       //Run the top task; if it returns true it needs to be repeated, so read task to the stack.
    }
}

My AI system is taking shape.

I've got a functioning child AI unit, but I won't show it until it's been cleaned up; it's using extremely messy pathfinding code which I'm not proud of yet.

[$trinick]

You've got more comments than you've got code, bro.

[McJob]

You've got more comments than you've got code, bro.

I'm demoing this code to my college of people who want but cannot program, so I need to really intricately explain every little detail.

I think the point here is that AI is really simple once you get the logic down.