Off Topic > Off Topic
Programming Megathread
ZSNO:
--- Quote from: McJob on March 05, 2016, 04:33:23 PM ---"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.
--- End quote ---
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.
Pecon:
--- Quote from: ZSNO on March 05, 2016, 09:45:33 PM ---can efficiently add and remove elements from the front and back of the element array because of the weird implementation.
--- End quote ---
I believe that this behavior is most commonly found in linked-list structures.
Ono-Sendai:
--- Quote from: Pecon on March 05, 2016, 11:57:59 PM ---I believe that this behavior is most commonly found in linked-list structures.
--- End quote ---
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:
--- Quote from: Pecon on March 05, 2016, 11:57:59 PM ---I believe that this behavior is most commonly found in linked-list structures.
--- End quote ---
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):
--- Quote from: McJob on March 09, 2016, 01:23:15 PM ---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.
--- End quote ---